Search taxonomy terms, not posts

Use get_terms() to retrieve terms that match your search query like :

$termsResult = get_terms( 'CUSTOM_TAXONOMY_NAME', 'search=SEARCH_QUERY' );

where,

CUSTOM_TAXONOMY_NAME is your custom taxonomy and
SEARCH_QUERY is the string which you are using to search for terms.

Afterwards you can generate list like :

if ( ! empty( $termsResult ) && ! is_wp_error( $termsResult ) ){
  echo '<ul>';
    foreach ( $termsResult as $term ) {
      echo '<li><a href="'.get_term_link( $term ).'">' . $term->name . '</a></li>';
    }
  echo '</ul>';
}