Yep, I'm afraid so, you have to do two queries, thou to speed things up you shouldn't do the full query each time...
First to get the total number of items from your query you'd use a count(*) statement instead of using the mysql_num_rows, this is was faster as it doesn't require all that nasty data transfer stuff and is handled internaly by MySQL.
SELECT COUNT(*) FROM ...
Then you would retrieve this value from the array like so
$row = mysql_fetch_array($result);
$count = $row["COUNT(*)"];
Next you would do your second query as normal, like so...
SELECT * FROM ... LIMIT 0,10
This seems to work quite fast and is almost unnoticable as far as my bench tests go.