At tælle alle rækkerne i en tabel er en meget langsom operation; du kan ikke virkelig fremskynde det, medmindre du er parat til at holde en optælling et andet sted (og det kan selvfølgelig blive ude af sync).
Folk, der er vant til MyISAM, har en tendens til at tro, at de får count(*) "gratis", men det er det egentlig ikke. MyISAM snyder ved ikke at have MVCC, hvilket gør det ret nemt.
Den forespørgsel, du viser, laver en fuld indeksscanning af et ikke-nul-indeks, hvilket generelt er den hurtigste måde at tælle rækkerne i en innodb-tabel på.
Det er svært at gætte ud fra de oplysninger, du har givet, hvad din applikation er, men generelt er det ok for brugere (osv.) at se tætte tilnærmelser af antallet af rækker i store tabeller.