Randomly Permute Elements in a List
Don't waste time on micro-optimizations. Use the simplest possible techniques that are known to perform well. In your specific case, it means replacing your multiple lists with one single array and using the standard fisher-yates-shuffle.
Naming conventions
In good C# code, local variables are camelCase beginning with a lower case letter. I renamed most of your variables to better express intent.

Generating the strings
You'll get a performance increase of about 30%-40% by using an array instead of a list (not much to be gained here).
Don't bother with string concatenation instead of string.Format, there is hardly any measurable difference in speed, but a huge difference in readability and maintainability.
string[] elements = new string[columns * rows];
for (int column = 0; column &lt; columns; column++)
    for (int row = 0; row &lt; rows; row++)
        elements[columns * row + row] = string.Format(&quot;{{{0},{1}}}&quot;, column, row);  


Shuffling them
Whenever you remove from a list, all the remaining elements have to be shifted to fill the gap. Use your array instead and use the fisher-yates-shuffle; don't attempt inventing your own.
for (int i = elements.Length - 1; i &gt; 0; i--)
{
    int swapIndex = random.Next(i + 1);
    string tmp = elements[i];
    elements[i] = elements[swapIndex];
    elements[swapIndex] = tmp;
}

This runs about 160 times as fast as your shuffling implementation.

Don't reinvent the wheel
When saving the results to disk, use File.WriteAllLines which does exactly what you were doing with the StreamWriter - in a single line.
File.WriteAllLines(outputFilename, elements);


Complete code (argument parsing omitted)
Once you've realized that a few milliseconds more or less don't matter, it would be good to split this up into several methods that each do exactly one thing. I'll leave that as an exercise to you.
string[] elements = new string[columns * rows];
for (int column = 0; column &lt; columns; column++)
    for (int row = 0; row &lt; rows; row++)
        elements[column*rows + row] = string.Format(&quot;{{{0},{1}}}&quot;, column, row);

Random random = new Random(seed);
for (int i = elements.Length - 1; i &gt; 0; i--)
{
    int swapIndex = random.Next(i + 1);
    string tmp = elements[i];
    elements[i] = elements[swapIndex];
    elements[swapIndex] = tmp;
}

File.WriteAllLines(outputFilename, elements);