Existe una manera mas "óptima" se saber el total de un query y consiste de usar SQL_CALC_FOUND_ROWS y FOUND_ROWS, esto según el manual de mysql y pruebas que he hecho.
La manera sería:
Código PHP:
$sql = "SELECT SQL_CALC_FOUND_ROWS
codigo, nombre
FROM usuarios";
$r = mysql_query($sql ); #Resourse al query
#Para el total haces:
$rTotal = mysql_query("select found_rows()");
$rsTotal = mysql_fetch_row($rTotal);
$total = $rsTotal[0];
mysql_free_result($rTotal);
PD: Tené en cuenta que SQL_CALC_FOUND_ROWS y FOUND_ROWS() están disponibles desde MySQL 4.x.x >.