I’ve written answer to How to paginate attachments in a secondary query as gallery?, which can be used for solving this problem. Like @wpmudev-ari said the [gallery] shortcode can be rewritten, or a new shortcode could be created. I explain below – B. – how this can be done. Additionally there is a very simple solution – A. – for the pagination of the shortcode.

A. Simple solution for paginating [gallery] shortcode

You can achieve pagination by using:

the numberposts and offset arguments of the shortcode;
in conjunction with the  tag;

like shown below.

Code:

[gallery numberposts="9"]
<!--nextpage-->
[gallery offset="9" numberposts="9"]

This actually doesn’t paginate the gallery, it paginates the post containing the gallery – or to be exact the splited gallery. But in some use cases this might just be enough, see the source for more details.

Source: Quick Tip: Paginate Your WordPress Gallery

B. Paginated by rewriting [gallery] or creating new shortcode

This assumes you want something like this:

|---------------------|   
|       content       |  
|       (static)      |  
|---------------------|  
|       gallery       |  
|       (paged)       |  
|---------------------|  
|   << pagelinks >>   |  
|---------------------|

1. Rewriting the [gallery] shortcode

Use either a) or b), not both.

a)

Code:

remove_shortcode('gallery', 'gallery_shortcode');
add_shortcode('gallery', 'wpse89462_get_attachment_gallery_shortcode');

b)

Code:

add_filter( 'post_gallery', 'wpse89462_get_attachment_gallery_shortcode', 10, 2 );

2. Creating a new shortcode

If you want to keep the original create a new one.

Code:

add_shortcode('wpse89462_paginated_attachment_gallery', 'wpse89462_get_attachment_gallery_shortcode');

3. Shortcode function

This functions runs if the shortcode is found.
Explanation for the gallery code can be found at above linked answer.

Code:

function wpse89462_get_attachment_gallery_shortcode( $output, $attr ) {
    global $post;

    static $instance = 0;
    $instance++;

    // We're trusting author input, so let's at least make sure it looks like a valid orderby statement
    if ( isset( $attr['orderby'] ) ) {
            $attr['orderby'] = sanitize_sql_orderby( $attr['orderby'] );
            if ( !$attr['orderby'] )
                    unset( $attr['orderby'] );
    }

    $html5 = current_theme_supports( 'html5', 'gallery' );
    extract(shortcode_atts(array(
        'posts_per_page' => 1, 
        'order'      => 'ASC',
        'orderby'    => 'menu_order ID',
        'id'         => $post ? $post->ID : 0,
        'itemtag'    => $html5 ? 'figure'     : 'dl',
        'icontag'    => $html5 ? 'div'        : 'dt',
        'captiontag' => $html5 ? 'figcaption' : 'dd',
        'columns'    => 3,
        'size'       => 'thumbnail',
        'post__in'    => '',
        'post__not_in'    => ''
    ), $attr));

    if ( ! empty( $post__in ) )
        $post__in = explode( ',', $post__in );

    if ( ! empty( $post__not_in ) )
        $post__not_in = explode( ',', $post__not_in );

    $id = intval($id);
    if ( 'RAND' == $order )
            $orderby = 'none';

    $output = '';

    $selector = "gallery-{$instance}";

    $gallery_style = $gallery_div = '';
    if ( apply_filters( 'use_default_gallery_style', ! $html5 ) ) {
        $gallery_style = "
         <style type='text/css'>
                #{$selector} {
                       margin: auto;
                }
                #{$selector} .gallery-item {
                        float: {$float};
                        margin-top: 10px;
                        text-align: center;
                        width: {$itemwidth}%;
                 }
                 #{$selector} img {
                        border: 2px solid #cfcfcf;
                 }
                 #{$selector} .gallery-caption {
                        margin-left: 0;
                 }
                 #{$selector}-pag-nav {
                 }
        </style>";
    }
    $size_class = sanitize_html_class( $size );
    $gallery_div = "<div id='$selector' class='gallery galleryid-{$id} gallery-columns-{$columns} gallery-size-{$size_class}'>";
    $gallery_nav_div = "<div id='{$selector}-pag-nav' class='gallery galleryid-{$id} gallery-size-{$size_class}'>";

    $gallery_page = (get_query_var('gallery_page')) ? get_query_var('gallery_page') : 1;

    $args = array(
        'posts_per_page' => $posts_per_page, 
        'order' => $order, 
        'orderby' => $orderby, 
        'post_type' => 'attachment',
        'post_status' => 'inherit', 
        'post_mime_type' => 'image', 
        'post_parent' => $id, 
        'paged' => $gallery_page,
        'post__in'    => $post__in,
        'post__not_in'    => $post__not_in
    ); 
    $gallery = new WP_Query($args);

        if ( $gallery->have_posts() ) :
            $output .= apply_filters( 'gallery_style', $gallery_style . "ntt" . $gallery_div );
                    while ( $gallery->have_posts() ) : $gallery->the_post();
                        $output .= wp_get_attachment_image( $post->ID, $size );
                    endwhile;
            $output .= '</div>';
            $output .= $gallery_nav_div;
                    if ( get_option('permalink_structure') ) {
                        $format = 'gallery/image/%#%';
                    } else {
                        $format = '&gallery_page=%#%';
                    }
                    $args = array(
                        'base' => get_permalink( $post->post_parent ) . '%_%',
                        'format' => $format,
                        'current' => $gallery_page,
                        'total' => $gallery->max_num_pages
                    );
                    $output .= paginate_links( $args );
                    wp_reset_postdata();
            $output .= '</div>';
        endif;
    return $output;
}

4. Additional code

Take a look at How to paginate attachments in a secondary query as gallery? for a explanation

a) Add a query variable

Code:

add_filter('init', 'wpse89462_attachment_gallery_add_query_var');
function wpse89462_attachment_gallery_add_query_var() {
    global $wp;
    $wp->add_query_var('gallery_page');
}

b) Rewrite

Code:

add_filter('init', 'wpse89462_attachment_gallery_add_rewrite_tag_rule');
function wpse89462_attachment_gallery_add_rewrite_tag_rule() {
    add_rewrite_tag('%gallery_page%','([^&]+)');
    // rewrite rules have to be added according to needs
    // below two rules are for two specitic cases
    // /{year}/{month}/{name}/[gallery_page rewrite]
    add_rewrite_rule('([0-9]{4})/([0-9]{2})/([^/]+)?/gallery/image//?([0-9]{1,})/?$', 'index.php?year=$matches[1]&month=$matches[2]&name=$matches[3]&gallery_page=$matches[4]', 'top');
    // /{name}/[gallery_page rewrite]
    add_rewrite_rule('([^/]+)/gallery/image//?([0-9]{1,})/?$', 'index.php?name=$matches[1]&gallery_page=$matches[2]', 'top');
}