Aggregate comments, with pagination

Most likely, the main thing that you missed is that you must have “Break comments into pages” checked in the Settings Discussion Subpanel. The pagination functions require this to be set, as do the URL rewrites.

Here’s a working, complete page template to do what you’re asking:

<?php
/*
Template Name: All Comments
See http://wordpress.stackexchange.com/questions/63770/aggregate-comments-with-pagination
*/
get_header(); ?>

<div id="content" role="main">

    <?php
    # The comment functions use the query var 'cpage', so we'll ensure that's set
    $page = intval( get_query_var( 'cpage' ) );
    if ( 0 == $page ) {
        $page = 1;
        set_query_var( 'cpage', $page );
    }

    # We'll do 10 comments per page...
    # Note that the 'page_comments' option in /wp-admin/options-discussion.php must be checked
    $comments_per_page = 10;
    $comments = get_comments( array( 'status' => 'approve' ) );
    ?>
    <ol start="<?php echo $comments_per_page * $page - $comments_per_page + 1 ?>">
        <?php wp_list_comments( array (
            'style' => 'ol',
            'per_page' => $comments_per_page,
            'page' => $page,
            'reverse_top_level' => false
        ), $comments ); ?>
    </ol>

    <?php # Now you can either use paginate_comments_links ... ?>
    <?php paginate_comments_links() ?>

    <?php # Or you can next/prev yourself... ?>
    <?php if ( get_comment_pages_count( $comments, $comments_per_page ) > 1 ) : // are there comments to navigate through ?>
    <nav id="comment-nav">
        <div class="nav-previous"><?php previous_comments_link( __( '&larr; Newer Comments' ) ); ?></div>
        <div class="nav-next"><?php next_comments_link( __( 'Older Comments &rarr;' ) ); ?></div>
    </nav>
    <?php endif; ?>

</div><!-- #content -->

<?php get_sidebar(); ?>
<?php get_footer(); ?>

If you didn’t want to globally enable comment pagination, it’s still possible, but it’s a minor headache because you’ll have to manually add the rewrites rules. Once you do that, you can fool WordPress into thinking that comment pagination is enabled via a simple filter,

add_filter( 'pre_option_page_comments', '__return_true' );