Larger validation sets give more accurate estimates of out-of-sample performance. But as you've noticed, at some point that estimate might be as accurate as you need it to be, and you can make some rough predictions as to the validation sample size you need to reach that point.
For simple correct/incorrect classification accuracy, you can calculate the standard error of the estimate as $\sqrt{p(1−p)/n}$ (standard deviation of a Bernouilli variable), where $p$ is the probability of a correct classification, and $n$ is the size of the validation set. Of course you don't know $p$, but you might have some idea of its range. E.g. let's say you expect an accuracy between 60-80%, and you want your estimates to have a standard error smaller than 0.1%:
$$
\sqrt{p(1−p)/n}<0.001
$$
How large should $n$ (the size of the validation set) be? For $p=0.6$ we get:
$$
n > \frac{0.6-0.6^2}{0.001^2}=240,000
$$
For $p=0.8$ we get:
$$
n > \frac{0.8-0.8^2}{0.001^2}=160,000
$$
So this tells us you could get away with using less than 5% of your 5 million data samples, for validation. This percentage goes down if you expect higher performance, or especially if you are satisfied with a lower standard error of your out-of-sample performance estimate (e.g. with $p=0.7$ and for a s.e. < 1%, you need only 2100 validation samples, or less than a twentieth of a percent of your data).
These calculations also showcase the point made by Tim in his answer, that the accuracy of your estimates depends on the absolute size of your validation set (i.e. on $n$), rather than its size relative to the training set.
(Also I might add that I'm assuming representative sampling here. If your data are very heterogeneous you might need to use larger validation sets just to make sure that the validation data includes all the same conditions etc. as your train & test data.)
