This seems to work OK:
SELECT `col1`, `col2`, (SELECT COUNT(*) FROM `table_name`) AS `count`
FROM `table_name` ORDER BY `col1` LIMIT 0, 20
You can grab the "count" value from any row, then mysql_data_seek() back to row 0 if necessary before looping through the results.