You could use paginate_links() to paginate the total gallery. This highly depends on your permalink settings. The best would be to check other answers on that topic here on WPSE.

Next/Prev post links for attachments.

Than there’s also the task to navigate on single attachment display.

Default API function/template tag

There’s the adjacent_post_link() function that can link to the next or previous post – an attachment is a post of the type “attachment”. It echos the output filtered by

apply_filters( "{$adjacent}_post_link", $format, $link );

where $adjacent is previous or next.

Example

adjacent_post_link( 
     '%link'        // format
    ,'%date/%title' // link
    ,false          // in_same_cat
    ,''             // excluded_categories
    ,false          // next/previous (previous = true)
);

Inner Details

If the post title of the attachment is empty, it gets replaced by a “Previous/Next Post” text. This title then has all the_title filter callback functions attached. You’d need to remove them if you don’t want this:

function wpse66660_attachment_remove_title_cbs( $title, $id )
{
    is_attachment() AND remove_all_filters( current_filter() );

    return $title;
}
add_filter( 'the_title', 'wpse66660_attachment_remove_title_cbs', 100, 2 );

Tags

As you’ve seen above ↑, there’re three “tags”, that you can use: %link, %date and %title.

The output of the function would be something like the following:

'<a href="'.get_permalink($post).'" rel="prev/next">' . $link . '</a>'

Now %title gets replaced by the post title and %date replaced by the post date. This allows you to add any custom value to the HTML-anchor tag.

The %link allows you to replace everything that is in the final string (HTML-anchor + link + rel + value) with something custom that aligns with your permalink settings.