Veo dos opciones.... una es tomar la función
wp_list_categories y colocarla en las dos sidebars, pero con la diferencia de que cada una tenga include a categorías diferentes como para no repetir.
La otra consistiría en utilizar algún plugin de jQuery como
Columnizer para dividir en dos el listado de categorías automáticamente (podés consultar mas en el
foro de frameworks de javascript)