In general, there is no theoretical upper bound on tests. This is a fundamental property of a good statistical test called consistency, i.e. a test is consistent if the power goes to 1 as n goes to infinity.
Most statisticians (myself included) rarely encounter the "problem" of having "n too big", and when presented with the problem, they're quick to say a standard approach would be stupid but not why. If we consider for a moment there are quite a few applications where this might happen. Suppose for instance, I am an industrial statistician measuring the clearance of interference valves on an engine to estimate the risk of the valve hitting the piston, I can design an experiment to run the engine at 12,000 RPMs for 1 hour using high speed cameras and get precision estimates for the clearances. The distribution will give me a probability of wear or give in the components causing a catastrophic failure.
To sum up I would propose 2 approaches.
- Put your alpha insanely low. This is a particularly good approach when using global tests such as AD. The point is that it's useless to declare a distribution as non-normal if it's practically very normal. That "choice" is very hard. You might just need to explore some simulations at various sample sizes, develop some metrics, and defend some subjective arguments. You can even say, "alpha=0.05 would work for N=100, so for N=100,000 I will choose alpha = 0.00005". The p value is not unstable, although your software needs some help reporting the actual p-value - use ODS export to get its result, or set alpha in the
/ options section.
- Use estimation instead of inference. With so many $n$, you can just get a kernel smoothed estimate of the density and say, "There it is!" without needing to declare whether it's normal or any other distribution. All the univariate statistics, like the mean, SD, IQR, min, max, can be viewed as probabilistic summaries of the empirical distribution function, so the idea of taking a sample and defining a distribution around is well defined.