カテゴリ一覧を出力しページ送りを追加

category.phpでページ送りを行うのは、メインクエリーで404になる可能性があるため、オススメできません。
固定ページでページテンプレートを作成する方が良いかと思います。前後ナビで良ければ以下のようなコードで。ページナビ系のプラグインを使う場合は、$wp_query->max_num_pages 等を書き換える必要が出てくるかと思います。

<?php
$items = 10;
$categories = get_terms( 'category', array(
	'orderby' => 'count',
	'hide_empty' => 0,
	'child_of' => 0,
	)
);
$max_page = ceil( count( $categories ) / $items );
$paged = get_query_var( 'paged' ) ? get_query_var( 'paged' ) : 1;
$categories = array_slice( $categories, ( $paged - 1 ) * $items, $items );
foreach($categories as $value):
?>
ループ内の記述
<?php endforeach; ?>
<?php
previous_posts_link();
next_posts_link( null, $max_page );
?>