Extend WordPress search with tax_query

I started with a basic query on my search template:

$query_args = array(
    'post_type' => 'listing',
    's' => get_query_var( 's' ),
    'posts_per_page' => 10,
    'paged' => $paged
);

The problem is that this only searches on the post name and content. Besides, if I look up something like 'rolling stones' I wouldn't get results containing only 'rolling' or only 'stones'. How can I make this more flexible so it shows listings containing ANY of the search terms, instead of ALL of them?

I also want to be able to search for listings using tags. For example, if I looked up 'rock', the listing "Rolling Stones" should come up, with many others also tagged with that term. I achieved this using the tax_query parameter, like this:

$query_args = array(
    'post_type' => 'listing',
    'tax_query' => array(
        'relation' => 'OR',
          array(
              'taxonomy'  => 'genre',
              'field'     => 'slug',
              'terms'     => array(...)
          ),
          array(
              'taxonomy'  => 'decade',
              'field'     => 'slug',
              'terms'     => array(...)
          )
    ),
    'posts_per_page' => 10,
    'paged' => $paged
);

Just assume that on those arrays in the terms parameter contain all the slugs for that taxonomy that are LIKE any of the search terms the user typed in the search bar (I get those doing something like get_terms( 'genre', array( 'name__like' => $search_term ) where $search_term is each of the words typed by the user in the search bar).

This second query works fine. However, when I try to combine both query arguments in a single query, I'm not getting the results I want. I assume this is because s and tax_query are being combined with an AND operator, so if I look up 'rock' it will try to find those listings tagged with rock and also have the word rock in their name or description.

So I need to do two things: 1) Make the first query more flexible so searching for 'rolling stones' would search for either 'rolling' or 'stones' in the title or description 2) Combine the two queries using an OR operator, so that searching for 'rolling stones' or 'rock' would both show me the band in the results.

I appreciate any guidance you can give me. I have read about doing the two queries separately and then combining then on the same array, but it concerns me that the order would be lost and I'm not sure if pagination would work this way.