paginate_links returns 404 page after $wp_rewrite

0
down vote
favorite
I’m using this code to paginate subcategory links and I’m trying to rewrite the URL so that it looks like this:

-> domain.com/mycategory-name/cpage/page_number/

instead of this:

-> domain.com/mycategory-name/?cpage=page_number

but I’m getting a 404 page.

I also have permanent links setup to /%postname%/ and I have flushed them before I test this. Why is this happening?

if ( get_category_children( $current_category->cat_ID ) != "" ) {
$args = array(
        'orderby' => 'id',
        'order'      => 'DESC',
        'hide_empty' => 1,
        'child_of'   => $current_category->cat_ID,);
$categories = get_categories($args);
$numOfItems = 20;
$page = isset( $_GET['cpage'] ) ? abs( (int) $_GET['cpage'] ) : 1;
$to = $page * $numOfItems;
$current = $to - $numOfItems;
$total = sizeof($categories);
$counter = 0;

for ($i=$current; $i<$to; ++$i) {
$category = $categories[$i];
$main = z_taxonomy_image_url($category->term_id, 'late-thumbnail'); 
$default = get_stylesheet_directory_uri().'/images/cats-images-na.png';
if ($category->name) { ?>

<a href="<?php echo get_category_link($category->term_id); ?>">
<div class="one_fourth<?php echo ( ++$counter == 4 )?' last_column':''; ?> home-colour" title="<?php echo $category->name; ?>">
<h2 style="text-align:center"> <?php echo $category->name; ?> </h2>
</div><!-- eof cat div --> </a>

<?php if ( $counter == 4 ) : ?>
<div class='clear'> </div>
<?php $counter = 0; endif; ?>

<?php }}} 
echo '<div class="clear"> </div>';
unset($category);
$pagination = array(
    'base' => add_query_arg( 'cpage', '%#%'),
    'format' => '',
    'prev_text' => __('&laquo;'),
    'next_text' => __('&raquo;'),
    'total' => ceil($total / $numOfItems),
    'current' => $page
);

if ( $wp_rewrite->using_permalinks() )
$pagination['base'] = user_trailingslashit( trailingslashit( remove_query_arg( 's', get_pagenum_link( 1 ) ) ) . 'cpage/%#%/', 'cpage' );
if ( !empty( $wp_query->query_vars['s'] ) )
$pagination['add_args'] = array( 's' => get_query_var( 's' ) );

echo paginate_links( $pagination );