Muchas gracias por tomarte el tiempo de responder, pero bueno no me referia a eso.
Al final he seguido haciendo pruebas esta mañana y dibujando en un papel como deberia ser la logica y al final lo he hecho asi:
<ul class="one">
<?php
$col = 1;
do {
?>
<?PHP
$sssssssss=number_format($totalRows_listar_paises/2,0);
if($col==$sssssssss+1){ echo "</ul><ul class=\"two\">"; }
echo "<li><a href=\"/"._SEO_ESTUDIAREN.urls_amigables($row_listar_paise s[$elidioma.'_pais'])."/".$row_listar_paises['id_pais']."\"><span>".$row_listar_paises[$elidioma.'_pais']."</span></a></li>";
?><?php $col++; } while ($row_listar_paises = mysql_fetch_assoc($listar_paises)); ?>
</ul>