But the opposite is equally possible: a terrible search tool could regularly fail to find what the user is looking for or produce music that they enjoy. In this situation, I can also imagine users searching more, because it takes more search effort to find something they like.
They key is why are users searching. In Spotify's case I imagine that you could try and connect number of searches per listen, or how often a search results in a listen and how often those listens result in a positive rating. There are probably more options, but there needs to be some way of connecting the amount of search with how the user feels about those search results.
And yeah, using nothing other than search volume is probably a bad way to go about it
The only way is to use the product yourself and honestly engage with it. Stats can't answer this question.
Nin, NIN, nine inch nails, Trent Reznor
VS
Nin, pantera, nail bomb, muse
This should be easy to differentiate, with a "[someone's name] distance algorithm" or such, right?