64 bit Mathematica does not have any practical limits on this. What limits you is the speed of your computer and the available memory. A $k\times k$ matrix will take a bit more than $8\times k^2 / 1024^3$ gigabytes of memory, so you see that a $10^6 \times 10^6$ matrix needs ~7500 GB of memory to store. You probably don't have that much in your computer.
As for the speed, start with smaller matrices, benchmark and increase the size slowly. Then you'll be able to to extrapolate how long a given size takes to solve on your computer, and you can make decisions about what computations to attempt.
From my previous experience, the size limit is somewhere between 25000-50000 unless you're prepared to wait for days. But don't trust me on it, measure! A twofold increase in matrix size will make the difference between a day or a week of computation time.