// Working with the query string
global $query_string;
$user_query_args = explode('&', $query_string );
$user_query_array = array();
if ( strlen( $query_string ) > 0 ) {
    foreach ( $user_query_args as $key => $string ) {
        $user_query_split = explode( '=', $string );
        $user_query_array[$user_query_split[0]] = urldecode( $user_query_split[1] );
    }
}

// Setting up `$paged`
global $paged;
$paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
if ( $paged === 1 ) {
    $offset = 0;
} else {
    $offset = ( $paged - 1 ) * $per_page;
}

// Args for user query
$user_args = array(
    'number' => $per_page,
    'offset' => $offset,
    'role' => 'Subscriber',
    'meta_query' => array(
        'relation' => 'OR',
        array(
            'key' => 'profile_service_1',
            'value' => $posts_str, // string of post IDs
            'compare' => 'IN'
        ),
        array(
            'key' => 'profile_service_2',
            'value' => $posts_str, // string of post IDs
            'compare' => 'IN'
        ),
    )
);

// Creating the user query
$users_query = new WP_User_Query( array_merge( $user_query_array, $user_args ) );
$users = $users_query->get_results();

if ( sizeof( $users ) > 0 ) {
    foreach ( $users as $user ) {
        // Here's where I show the user stuff
    }
}

// Setting up pagination
$total_users = $users_query->total_users;
$total_pages = ceil( $total_users / $per_page );

$pagination_args = array(
    'base' => @add_query_arg('paged','%#%'),
    'format' => '?paged=%#%',
    'current' => $paged,
    'total' => $total_pages,
    'prev_text' => 'Previous',
    'next_text' => 'Next',
    'type'     => 'list',
);

if ( $wp_rewrite->using_permalinks() ) {
    $pagination['base'] = user_trailingslashit( trailingslashit( remove_query_arg( 's', get_pagenum_link( 1 ) ) ).'page/%#%/', 'paged' );
}

if ( ! empty( $wp_query->query_vars['s'] ) ) {
    $pagination['add_args'] = array( 's' => get_query_var( 's' ) );
}

echo paginate_links( $pagination_args );