If you're using MySQL, there's a nice SQL_CALC_FOUND_ROWS additional option to SELECT. It counts the rows that would be returned without LIMIT. It can be used like this:

SELECT col1, col2, col3 FROM a_table LIMIT 0, 10 SQL_CALC_FOUND_ROWS; 
+=> your normal resultset
SELECT FOUND_ROWS(); => total number of rows returned
[download]