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 />";
}