Having trouble with using add_rewrite_rule and pagination

Your rewrite rules are good, but the redirect happens because WordPress applies canonical redirect via its redirect_canonical() function which is hooked to template_redirect.

And you can cancel the redirect via the parse_request action, like so, where we check if the matched rewrite rule is the one you set when you call add_rewrite_rule() and if it is, then cancel the redirect by “unhooking” redirect_canonical() from the template_redirect action:

add_action( 'parse_request', function( $wp ){
    if ( 'for-sale\/([a-z-]+)\/([0-9])+\/?$' === $wp->matched_rule ) {
        remove_action( 'template_redirect', 'redirect_canonical' );
    }
} );