wp_list_categories

Here is some code that illustrates using paginate_links() to paginate an array. This may get you started:

$rows_per_page = 7;
$current = (intval(get_query_var('paged'))) ? intval(get_query_var('paged')) : 1;

$catlist = wp_list_categories('echo=0&style=none');
$rows = explode('<br />', $catlist);

global $wp_rewrite;

$pagination_args = array(
 'base' => @add_query_arg('paged','%#%'),
 'format' => '',
 'total' => ceil(sizeof($rows)/$rows_per_page),
 'current' => $current,
 'show_all' => false,
 'type' => 'plain',
);

if( $wp_rewrite->using_permalinks() )
 $pagination_args['base'] = user_trailingslashit( trailingslashit( remove_query_arg('s',get_pagenum_link(1) ) ) . 'page/%#%/', 'paged');

if( !empty($wp_query->query_vars['s']) )
 $pagination_args['add_args'] = array('s'=>get_query_var('s'));

echo paginate_links($pagination_args);

$start = ($current - 1) * $rows_per_page;
$end = $start + $rows_per_page;
$end = (sizeof($rows) < $end) ? sizeof($rows) : $end;

echo '<br />';
for ($i=$start;$i < $end ;++$i ) {
   $row = $rows[$i];
   echo "$row<br />";
}