Mysql cuenta el rendimiento en tablas muy grandes

No pareces interesado en el recuento real, así que prueba esto:

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

Si se devuelve una fila, tiene 5000 y más registros. Supongo que el fk la columna está indexada.