Redirect early

First of all, your redirect function should be hooked early: you are not relying on query variables there, so you could use init hook:

function search_redirect() {
    if (!empty($_GET['s'])) {
       $home = trailingslashit(home_url('catalog-of-work'));
       wp_safe_redirect($home.urlencode(get_query_var('s')));
       exit();
    }   
}

add_action('init', 'search_redirect');

The reason is that this will redirect the request much earlier, saving a lot of processing.

Set query variables properly

Now, you need to tell WordPress that when the URL /catalog-of-work is visited, it has to consider a search request.

function custom_search_query_var($do, $wp) {
    $path = trim(parse_url(esc_url_raw(add_query_arg([])), PHP_URL_PATH), "https://wordpress.stackexchange.com/");
    $home_path = trim(parse_url(esc_url_raw(home_url()), PHP_URL_PATH), "https://wordpress.stackexchange.com/");
    $home_path and $path = trim(substr($path, strlen($home_path)), "https://wordpress.stackexchange.com/");
    if (strpos($path, 'catalog-of-work') === 0) {
        $wp->query_vars['s'] = trim(substr($path, 15), "https://wordpress.stackexchange.com/");
        $do = false;
    }

    return $do;
}

add_action('do_parse_request', 'custom_search_query_var', 10, 2);

There are some things to note in the code above:

• I used do_parse_request hook instead of parse_request. This allows me to completely prevent WordPress parsing rules whe the URL /catalog-of-work is visited. Since processing query vars can be a slow process, this could improve your page performance.
• My logic to determine current URL make use of add_query_arg instead of directing access to $_SERVER. That’s better because the function takes care of some edge cases.
• My logic handles the case that your home URL is something like example.com/wp instead of example.com. Since the home URL can easily be changed, this ensure that the function is more stable and will work in different situations.
• The code I used sets the “s” query var in the $wp->query_vars array. $wp is the current instance of WP class that is passed by do_parse_request hook. This is better for two reasons:
  1. you avoid to access global variables directly
  2. setting variables to global $wp_query is not reliable on do_parse_request (neither on parse_request you used) because that hooks happen before $wp_query is processed and some reset may still happen there, deleting the s query var. By setting the query var to $wp object, it will take care to pass variables to $wp_query.

Prevent 404

Doing things like I described, having a 404 template does not affect anything, because WordPress do not set 404 status for search queries.

However, my code (just like your code, at least the code you posted) does not act on the template so, by default, WordPress will load search.php.

It is very possible that your search.php template (or the template you are using) checks for have_posts() and load 404 template (if found) when there are no posts.

That really depends on the theme you are using.

For example, the theme Twentyfifteen, contains something like:

<?php if ( have_posts() ) : ?>
    // ... redacted loop code here...    
else :
    // If no content, include the "No posts found" template.
    get_template_part( 'content', 'none' );
endif;
?>

If your theme contains something like this, 404 template could be loaded when there are no posts, which happens when the search query is empty.

If that is the issue, you should edit your search template (or if the theme is third party or a core theme you should create a child theme) to make the search template handle the case of no posts according to your needs.