Nevermind, figured it out:
<?php
$cats = explode("<br />",wp_list_categories('title_li=&echo=0&depth=1&style=none&show_count=1'));
$cat_n = count($cats) - 1;
$cat_col = round($cat_n / 2);
for ($i=0;$i<$cat_n;$i++){
if ($i<$cat_col){
$cat_left = $cat_left.'<li>'.$cats[$i].'</li>';
}
elseif ($i>=$cat_col){
$cat_right = $cat_right.'<li>'.$cats[$i].'</li>';
}
}
?>
<table border="0" width="260"><tr>
<td><ul>
<?php echo $cat_left;?>
</ul></td>
<td><ul>
<?php echo $cat_right;?>
</ul></td>
</tr></table>