Your first problem is: you have completely the wrong approach.
Quote:When a user has many thousands of items selected in a DataGridView (we're talking hundreds of thousands or even millions)
Do you seriously think that any user will conscientiously select that many records? That he will even look at that many records?
That he has the time to wait for that many records to be displayed - and that will take a significant amount of time?
Never mind about improving your processing speed - think of the poor user who is faced with thousands or even millions of rows of data and what exactly you are expecting him to do with it? Are they going to go "that one, and that one, but not that one" for each row? or "Select all" and move on? And if they are going to select all of them, why are you wasting their time and effort displaying that many?
And then look at your error message: it's telling you that what you are trying to convert is a generic collection, not a list. Try calling ToList on the collection ...
But converting it to Linq won't solve your problem, it just "hides" the loop - it doesn't remove it at all!