Mysql conta le prestazioni su tavoli molto grandi

Non sembri interessato al conteggio effettivo, quindi prova questo:

SELECT 1 FROM table WHERE fk = 1 LIMIT 5000, 1

Se viene restituita una riga, hai 5000 e più record. Presumo il fk la colonna è indicizzata.