paginate_links method doesn’t show second page of my custom wp_query

You’ll have a much easier time if you use the main query, and add your extra filters with pre_get_posts.

So first of all, just use search.php as your template, and use the main query. So no new WP_Query(), and use the have_posts() and the_post() functions, not the methods.

So your template (simplified) would be like this:

if ( have_posts() ) {
    while ( have_posts() ) {
        the_post();
        // etc.
    }
}

echo paginate_links();

wp_reset_postdata();

Then change the txt_title field to use the native s name for searches.

Then, to handle the extra search parameters, use the pre_get_posts hook:

function wpse_338980_search( $query ) {
    if ( is_admin() ) {
        return;
    }

    if ( $query->is_search() ) {
        $query->set( 'posts_per_page', 4 );

        if ( isset( $_POST['sel_year'] ) && isset( $_POST['sel_platform'] ) ) {
            $query->set( 'category_name', $_POST['sel_year'] . '+' . $_POST['sel_platform'] );
        }

        if ( isset( $_POST['txt_genre'] ) ) {
            $query->set( 'tag', $_POST['txt_genre'] );
        }
    }
}
add_action( 'pre_get_posts', 'wpse_338980_search' );

Doing it that way means that the main query is being properly filtered according to your search parameters, and because it’s the main query the pagination functions will work out of the box.