Iterating thousands of times over large collections: advices
If you are particularly interested in doing substring look-ups, you could look into the Trie data structure.  You will be stuck writing your own, however, as there is no implementation I know of in the BCL.

Alternatively, if you just want to put something together quick, you could just use a normal, single-level-deep dictionary keyed by file name.  If you build your dictionary for existing MP3s first using an actual System.Collections.Hashtable or (preferably) System.Collections.Generic.Dictionary&lt;TKey,TValue&gt;, the key lookups will be constant-time.

The only loops you will need are the initial loop to build the correct file path dictionary, then the loops over .m3u files with sub-loops over their referenced files.  Retrieving the correct mp3 reference for each file in a m3u is just value = dictionary [key] or dictionary.TryGetValue (key, out value).  The lookups themselves are not loops - rather, they generate hash codes for the keys which ultimately translate to array indexes in the underlying data structure.