I found where the search and comparison takes place in the plugin and it turns out that you are using strtolower(), which is not friendly with the Cyrillic alphabet. Can you fix it in the plugin and release an update with the mb_strtolower() function?
This is my fix:

// Used strtolower() because, If search term is 'product' and actual taxonomy title is 'Product',
      // Then, it does not match due to its case sensitive test.
      if (($strict && mb_strtolower($term->name) == mb_strtolower($search_term)) || (!$strict && strpos(mb_strtolower($term->name), mb_strtolower($search_term)) !== false))