If you're going to be saving into a database anyway, why don't you just bulk import your data and use queries to join the two sets of data? That should perform much faster than trying to do it in memory. I would hate to see the memory you are consuming with millions of entities.
If you must do it in memory, using PLinq MAY prove to be faster. There is an overhead to thread creation and context switching. With PLinq, you should let the engine determine the thread allocations. You should rarely create threads explicitly at this point.
However, if the list you are comparing against is relatively static, you may benefit more from making it a dictionary and relying on the key for the lookup as you won't have to scan through the entire list for each item you are trying to find.