Quand on a toutes les données, ça change tout : dans ce cas tu peux utiliser la fonctionnalité SQL_CALC_FOUND_ROWS et la fonction FOUND_ROWS().
Tu fais toujours 2 "requêtes" mais la seconde n'est qu'un appel de la fonction FOUND_ROWS pour lequel MySQL t'auras gardé le résultat du SQL_CALC_FOUND_ROWS (une espèce de COUNT interne ignorant la clause LIMIT) au chaud.
Pour résumer :
- une première requête en : SELECT SQL_CALC_FOUND_ROWS colonne1 FROM table ... LIMIT ... (c'est juste un mot clé en plus qui suit SELECT en somme par rapport à ton SELECT de base/origine)
- une deuxième pour invoquer FOUND_ROWS : SELECT FOUND_ROWS() (à exécuter puis en faire un fetch pour récupérer ce nombre bien sûr)
Pour les détails, voir la doc de MySQL.
(si tu n'arrives pas à l'intégrer, repasses avec ton code )