This sounds like a great use-case for MiniSearch, a client-side full-text search engine written in JavaScript, small enough to run in the browser and with zero dependencies (disclaimer: I am the author of the library).
MiniSearch is routinely used for searching amongst tens of thousands of small items (e.g. all products in the catalog of a supplier), and the data can be indexed upon each page load (it usually takes sub-second, and can be done asynchronously).
Here’s a demo on a database of ~5000 songs.
