Para agregar el título que diga categoría solo debes agregar una pequeña línea.
Código:
<?php
$cats = explode("<br />",wp_list_categories('title_li=&echo=0&depth=1&style=none'));
$cat_n = count($cats) - 1;
for ($i=0;$i<$cat_n;$i++):
if ($i<$cat_n/2):
$cat_left = $cat_left.'<li>'.$cats[$i].'</li>';
elseif ($i>=$cat_n/2):
$cat_right = $cat_right.'<li>'.$cats[$i].'</li>';
endif;
endfor;
?>
<h1>Categorias</h1>
<ul class="left">
<?php echo $cat_left;?>
</ul>
<ul class="right">
<?php echo $cat_right;?>
</ul>
en cuanto a que estan muy separadas, es cosa de tu css ( style.css de tu theme) , para poderte ayudar, deja tu web, para ver que debes cambiar en tu style.css
Salu2!