Pagination on custom post type not working if permalinks set to rewrite url

This issue was reported here : https://core.trac.wordpress.org/ticket/15551

It comes from the redirect_canonical() WP function.

Try to disable canonical redirect for your custom post type to get pagination work :

add_filter( 'redirect_canonical','custom_disable_redirect_canonical' ); 
function custom_disable_redirect_canonical( $redirect_url ){
    if ( is_singular('your_custom_post_type') ) $redirect_url = false;
    return $redirect_url;
}

Hope that helps.