It depends on the type of system you're trying to solve. Is it sparse, is it dense, is it structured? There are two limiting factors: how much memory you have to store the system, and how many operations are required to perform the solve.
For a sparse symmetric system, plain old Gaussian elimination or LU decomposition can solve the system in O(n) complexity, for just sparse I think you can get as low as O(n^1.2), and for a dense system they have complexity O(n^3) and require memory storage of O(n^2), where n is the size of the system.
There are much better iterative methods that can solve sparse symmetric in O(kn), sparse in O(k^2 n), and dense systems in O(k n^2) complexity and O(k n^2) memory required straight out of the box. Here k is the number of iterations. If you precondition the system properly k << n and the k is negligable, and in the worst case scenario k = n.
However, there are ways to cheat and get down to O(nlogn) for complexitiy and memory.
You should be able to solve a system of a few hundred equations almost instantaneously. As long as you have enough memory to store the procedure, it will just start to take longer and longer as the system grows. For a dense system of size 100,000 you better use an iterative method with a good preconditioner. And once you get to size one million, which is too large to store in memory, there are other tricks to get around that if your system comes from some structured layout and doesn't need to be stored all at once.
I don't know about mathematica, but in MATLAB I think the default method is GE. If you specify a sparse matrix, it may use the sparse methods. Beyond that I think you need to use your own program for the other methods.
