Solucionado.
Lo pongo por si a alguien le pudiera servir:
Código:
$sql = "select distinct city from sho where city like 'M%'";
$sql2 = "select city from accommodation where city like 'M%'";
$result = mysql_query($sql,$db_con);
$total = mysql_num_rows($result);
$count = mysql_query($sql2);
while(($row = mysql_fetch_array($result)) && ($total = mysql_num_rows($count)))
{
echo '<tr>
<td><a href=rest.php?city='.urlencode($row["city"]).'>'.$row["city"].'</a> <em><strong>'.$total.'</strong></em></td>
</tr>';
}
mysql_free_result($result);
?>