I love your idea, and it is used in other examples as well. (The LDS has a Gospel Library app, with a digital hymn book, that functions in a similar fashion.) But I have a few ideas to add, if they sound decent.
This first idea is related to Google's Instant Results. Pretend I'm looking for hymn... #314, let's go with that. What if you made it so when I write 3, it lists hymns 3, 30-39, and 300-399? Then, I write 31, so it lists 31, and 310-319. I don't know what it's called, but that's one idea. It lists everything that starts with what was written. In this case, if I wanted 314, I'd write 3, 1, and see the link to 314. 3 clicks, done.
Another idea is to count how many times each hymn file was opened this month, and delete counts more than a month old. (Change this as applicable. How often should it be used?) Then, on the main page, have a "sort by commonly used" or "sort by popular" or whatever button. List the ones with highest count first, and if there's a tie, fallback to numerical.
Also, categories are a MUST with huge indexes, especially if exploration is involved. Why not provide filters based on topic?