OK, after no luck with wp_list_categories, I resorted to get_categories to get the pagination working. I hope this helps someone.
<?php
$args = array(
'taxonomy' => 'categories',
'orderby' => 'term_group',
'hide_empty' => 0,
'hierarchical' => 1,
'exclude' => '16',
'parent' => '0',
);
$categories = get_categories($args);
$numOfItems = 60;
$page = isset( $_GET['cpage'] ) ? abs( (int) $_GET['cpage'] ) : 1;
$to = $page * $numOfItems;
$current = $to - $numOfItems;
$total = sizeof($categories);
echo '<ul class="content">';
for ($i=$current; $i<$to; ++$i) {
$category = $categories[$i];
if ($category->name) { echo '<li><a href="' . get_term_link($category->slug, 'categories') . '" title="' . sprintf( __( "View all posts in %s" ), $category->name ) . '" ' . '>' . $category->name.'</a></li>';}
}
echo '</ul>';
unset($category);
echo paginate_links( array(
'base' => add_query_arg( 'cpage', '%#%' ),
'format' => '',
'prev_text' => __('«'),
'next_text' => __('»'),
'total' => ceil($total / $numOfItems),
'current' => $page
));
?>