Hola,
No es solo el numero de registros, sino el tamaño de cada registro. Un SELECT * trae todos los datos, asi que lo mas posible es que el tamaño total de la consulta sea demasiado grande.
Y si es para una paginacion, lo mejor es hacer 2 consultas separadas:
1.- Para contar el numero total de registros:
SELECT COUNT(*) FROM tabla WHERE loquesea
2.- Para leer solo los registros que muestras por pagina:
SELECT * FROM tabla WHERE loquesea ORDER BY loquesea LIMIT
primer_registro_a_mostrar,
numero_de_registros_a_mostrar
Mas info:
www.mysql.com/select
Saludos.