Tamam işte hocam;

echo "<ul class=\"pagination\">";

for($i = 1; $i < 5; $i++)
{
     echo "<li class=\"aaaa\"><a rel=\"$i\" href=\"#\">$i</a></li>";
}

echo "</ul>";
yaparsanız olacaktır istediğiniz gibi.

<ul> ler for dışında kalacak.