Solution:1
Take a look at SQL_CALC_FOUND_ROWS
Solution:2
SELECT COUNT(*) FROM table_name WHERE column = 'value'
will return the total number of records in a table matching that condition very quickly.
Database SELECT
operations are usually “cheap” (resource-wise), so don’t feel too bad about using them in a reasonable manner.
EDIT: Added WHERE
after the OP mentioned that they need that feature.