The efficient frontier is mostly an imaginary (or theoretical) shape. The primary problem is not the number of possible portfolios. Modern computers can compute hundreds of millions of possible mixtures quite quickly, and the probability that there is some magic overlooked non-data-mined portfolio combination which defies the trends outlined by hundreds of millions of other ones (in a good direction) is pretty small.
The problem is what to do with the mixture once you have picked one, or a few million?
Since it is supposed to be an expectation about the future, it cannot be computed empirically as the future has not yet happened. It can be computed theoretically by assuming the historical means, variances, and co-variances can be projected into the future (along with several other assumptions, many of which are rather dubious).
You could try to construct it with historical data, but this also has many pitfalls.
For example, if you know the returns for the past 15 years for each candidate stock in the portfolio, it is easy to compute the average return of a given portfolio over those 15 years. But where do you get the variance? The return of a give portfolio over the past 15 year is exactly whatever it is--there is no variance.
You could take 15 slices each of 1 year to compute the variance over, but then you have the shape of a Markowitz bullet for the time period of 1 year. What good is that? If you are investing for 1 year, just put it in a savings account and forget about it. You could use theory to extrapolate that out to longer periods, but doing that requires making assumptions we (or I, anyway) don't actually believe to be true.
You could try to construct 15 time slices of 15 years each, but when going back 225 years, how good is your data, really? And how do you account for survivorship bias, not only of companies, but of entire nations?
So the precise shape of the efficient frontier is mostly an imaginary thing. But, how much does that matter? If you accept that is it kind of parabolic-ish, does it matter exactly where the directix, the focus, and the latus rectum is? I don't think it does, as it still says diversification is better than not, even if you can't quantify the exact degree.
So rather than being imaginary or theoretical, perhaps it is best characterized as pedagogical.