Wordpress category posts with pagenation in page template

I'm using the code below to display in a custom page, a list with posts from a certain category. I would like to add pagenation at the bottom, but until now, I fail.

Any way to add it somehow?

           <?php $cat_id = 22;
             $cat_link = get_category_link( $cat_id );
             $cat_name = get_cat_name($cat_id); ?>


       <div class="catrecent">
           <?php    $query = new wp_query();
           $query->query('showposts=1&cat=' .  $cat_id);
           if ($query->have_posts()) : while ($query->have_posts()) : $query->the_post(); ?>
               <div class="recenttitle">
                   <h2 class="catidtxt"> <a href="<?php echo ($cat_link); ?>" title="<?php echo ($cat_name); ?>"><?php echo ($cat_name); ?></a></h2>
                   <h2 class="recentposttitle"><a href="<?php the_permalink(); ?>" rel="bookmark"><?php the_title(); ?></a></h3>    
               </div>

               <div class="recentpostwrap">
                    <?php the_post_thumbnail( 'catlarge' ); ?>
                    <?php the_content_limit(600,""); ?>
               </div>


              <?php endwhile; else: ?><?php endif; ?><?php wp_reset_query(); ?>
       </div>

       <ul class="posts_list"> 
           <?php    $query = new wp_query();
           $query->query('offset=1&showposts=4&cat=22&paged=' .  $cat_id);
           if ($query->have_posts()) : while ($query->have_posts()) : $query->the_post(); ?>

                                <li>
                                    <a href="<?php the_permalink(); ?>"><?php the_post_thumbnail( 'catmed' ); ?></a>
                                    <a href="<?php the_permalink(); ?>" rel="bookmark"> <?php the_title(); ?> </a>
                                </li>

           <?php endwhile; else: ?><?php endif; ?><?php wp_reset_query(); ?>
       </ul>

Solution

Useful links: http://codex.wordpress.org/Function_Reference/paginate_links, http://codex.wordpress.org/Making_Custom_Queries_using_Offset_and_Pagination

Try something like this

<ul class="posts_list"> 
    <?php
    $paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
    $ppp = 4;
    $offset = 1;

    //Manually determine page query offset (offset + current page (minus one) x posts per page)
    $page_offset = $offset + ( ($paged - 1) * $ppp );

    $query = new wp_query(array(
        'offset'         => $page_offset,
        'posts_per_page' => $ppp,
        'cat'            => $cat_id,
        'paged'          => $paged
    ));

    if ($query->have_posts()) : while ($query->have_posts()) : $query->the_post(); ?>

    <li>
        <a href="<?php the_permalink(); ?>"><?php the_post_thumbnail( 'catmed' ); ?></a>
        <a href="<?php the_permalink(); ?>" rel="bookmark"> <?php the_title(); ?> </a>
    </li>

    <?php endwhile; else: ?><?php endif; ?>
</ul>

<?php
// pagination
$big = 999999999; // need an unlikely integer
echo paginate_links(array(
    'base'    => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) )    ),
    'total'   => ceil(($query->found_posts - $offset) / $ppp),
    'format'  => '?paged=%#%',
    'current' => max( 1, get_query_var('paged') ),
));

wp_reset_query();