WordPress pagination not working on template search.php

Question

I have a small issue, pagination doesn't work on search.php. I query the results with wp_Query using the code below, I get to see the page link but when I press them I get 404 error. I was told that this happens becouse I query on the search.php page.

The code I'm using is taken from the wp code pagination, Its a long query but what is important are these two lines:

$paged = ( get_query_var( 'paged' ) ) ? absint( get_query_var( 'paged' ) ) : 1;

and

'paged' => $paged,

complete query

if (isset($_GET['reg-prop-search-form'])){
    $paged = ( get_query_var( 'paged' ) ) ? absint( get_query_var( 'paged' ) ) : 1;


    $args = array(
        'posts_per_page' => 9,
        's' => $_GET['s'],
        'post_type'      => 'property',
        'paged' => $paged,
        'meta_query'     =>  array(
            'relation '  => 'AND',
            array(
                'key'       => 'prop_area',
                'value'     => $area,
                'compare'   => $area_val,
            ),
            array(
                'key'       => 'prop_city',
                'value'     => $city,
                'compare'   => $city_val,
            ),
            array(
                'key'       => 'prop_type',
                'value'     => $type,
                'compare'   => $type_val,
            ),
            array(
                'key'     => 'prop_rooms',
                'value'   => array( $fromrooms, $torooms ),
                'type'    => 'numeric',
                'compare' => 'BETWEEN',
            ),
            array(
                'key'     => 'prop_store',
                'value'   => array( $fromfloor, $tofloor ),
                'type'    => 'numeric',
                'compare' => 'BETWEEN',
            ),
            array(
                'key'     => 'prop_price',
                'value'   => array( $min, $max ),
                'type'    => 'numeric',
                'compare' => $equal,
            ),
        ),
    );  
};

this is the loop

$the_query = new WP_Query( $args );

.....

    <?php if( $the_query->have_posts() ): ?>
        <?php while( $the_query->have_posts() ) : $the_query->the_post(); ?>


            <?php get_template_part( 'content', 'search' ); ?>

        <?php endwhile; ?>
    <div id="pagination">

        <?php

            $big = 999999999;
             echo paginate_links( array(
                'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
                'format' => '?paged=%#%',
                'current' => max( 1, get_query_var('paged') ),
                'total' => $the_query->max_num_pages
            ) );
        ?>
        <?php echo paginate_links( $args ); ?>


    </div>
    <?php else : ?>

        <?php get_template_part( 'no-results', 'search' ); ?>

    <?php endif; ?>
    <?php wp_reset_query();  // Restore global post data stomped by the_post(). ?>
</div>