You could try this plugin:
https://wordpress.org/plugins/wp-pagination/
It makes a javascript approach to paging.
For my projects i always started to build galleries using custom post types or repeaterfields with acf:
http://www.advancedcustomfields.com/add-ons/repeater-field/
WordPress built in gallery function is… well almost unfunctional. 🙂