I tried out a few simple tests on your site and couldn't establish what the issue is, and I don't want to go any further any break anything, so I'm taking a copy I can work on locally for debugging.
I'll update you again in a little while.
(By the way I noticed some of your plugins are not up-to-date, including Views, and you should update them.)
On the locally installed copy, after updating plugins, the search appears to be working correctly on a minimal install (i.e. I started with just Types and Views active, then activated WPML, then activated Relevanssi and the results were as expected in each case).
Can you please try the same—update plugins then check with minimal install.
If that's OK you can go ahead and re-activate your other plugins to see if any of them break the search because of some conflict, or whether they all can be re-activated now that the plugins are up-to-date.
* I deactivated all plugins except: Toolset plugins, WPML plugins, and Relevanssi.
The search is not working properly.
For example, it works for the Hebrew search term "אבא", but not for the search term "אביר".
My only thoughts on the matter is that the song with the latter Hebrew search term in its title was uploaded months after much of the other songs.
I uploaded these songs as txt files. They appeared as posts. Then, using the plugin Convert Post Types, I converted them to Songs (a custom post type I created with Toolset).
These Songs appear fine, and many of them appear in the search results.
Obviously this is a little tricky for me because of the Hebrew, but can you confirm from these two screenshots that the results are expected on my local site for *both* of these search terms?
I went on to your staging site and confirmed that the search for אביר was not working.
After disabling Relevanssi I tried again and it worked.
So I rebuilt the Relevanssi index after re-activating and tried again and it still did not work.
I noted in the Relevanssi settings that the song posts are not included in the index. I added them to be indexed, re-indexed the site, and now the search appears to be working with minimal install.
Can you go ahead and re-activate everything you need and keep testing to confirm that it still works?