If you want to split categories across sidebars, then the easiest way is to group them differently.
For example, you could make a category called Left and another called Right. The make all your other categories children of those two.
Then, find the ID numbers of Left and Right. To then show only the categories under one of those, you'd do something similar to this:
wp_list_cats('sort_column=name&child_of=XXX');
...where XXX is the ID of either Left or Right.
An alternative method that doesn't use groupings like this would simply be to exclude the categories you don't want to display on each side:
wp_list_cats('sort_column=name&exclude=10, 15');
... that would display the categories but not display the categories with ID's 10 and 15, for example.
More options are covered in the codex: http://codex.wordpress.org/Template_Tags/wp_list_cats