Admin: WooCommerce Navigation Menus do not show empty categories search tab

When you perform a search for terms in the menu editor, it runs get_terms() with the name__like argument (a category is a type of “term”).

The get_terms_args filter lets you filter any use of get_terms(). So we can use this filter and check if the name__like argument has a value. If it does then that tells us this is a search for a term, in which case we will force the query to include empty terms:

function wpse_327345_search_empty_terms( $args, $taxonomies ) {
    if ( ! empty( $args['name__like'] ) ) {
        $args['hide_empty'] = false;
    }

    return $args;
}
add_filter( 'get_terms_args', 'wpse_327345_search_empty_terms', 10, 2 );

Note however that this will also affect searches for terms in other areas of the admin, like the post edit screen and categories list. If you only want to include empty terms when searching from the menu editor, you can check if the query is part of the AJAX request that performs the search by checking if $_POST['action'] is exists and equals menu-quick-search:

function wpse_327345_search_empty_terms( $args, $taxonomies ) {
    if ( isset( $_POST['action'] ) && $_POST['action'] === 'menu-quick-search' ) {
        if ( ! empty( $args['name__like'] ) ) {
            $args['hide_empty'] = false;
        }
    }

    return $args;
}
add_filter( 'get_terms_args', 'wpse_327345_search_empty_terms', 10, 2 );