I would say:
Sample the incoming signal at 20 MHz.
Every time you detect a transition in the input signal, take the value of a counter, that is incremented at every tick of the 20 MHz clock, and add it to a list of values, for which you will compute average and standard deviation. After that, reset that same counter.
So, basically, measure the average and the standard deviation of the random variable "time between consecutive transitions". If those are equal to 0.5 us and 0 us, respectively, the incoming signal is a very clean 1 MHz signal. The higher the standard deviation, the "dirtier" the incoming signal is, to be used as a clock. You can also use the minimum and maximum of those values in the list. The larger the distance between min and max, the worse.
There are ways to compute (of course) average and (also) standard deviation, without having to keep all the list of values in memory. See this Rapid calculation methods section.
Given that, with an FPGA, it won't be easy to do square roots, don't do them. Just work with the square of the standard deviation. Comparing them will be equally useful. Or even just work with min and max, although that will make you loose subtle nuances.
If you work with a time window that has \$2^N\$ samples, you'll be able to average without doing any division (just doing shifts to the right). You can keep the average of the random variable, and then, for each new value of the counter, instead of computing the official standard deviation, just compute the absolute value of the difference between your incoming sample, and the current average, and finally compute the average of those absolute values. That will give you something similar to an standard deviation, but that requires no multiplications, squares, square roots, or divisions. Only additions/subtractions, absolute values, and shifts to the right. Very easy.
Second method: build a histogram of that random variable. So, in the horizontal axis you will have "time (in 20 MHz ticks) between consecutive transitions", and in the vertical axis you will have "number of events". Every time you detect an input transition, get the value in the counter, find the x position in the histogram that corresponds to that value, increment the histogram value by one, and reset the counter. Every once in a while, evaluate the histogram, and then reset it. Imagine that the x axis goes from 1 tick to 20 ticks. A clean 1 MHz signal will increase only the "10 ticks" slot of the histogram. Imagine a thin band centered around the 10 ticks slot. Count the number of events outside that band. The higher that number, the dirtier the signal will be. This involves fewer computations, and is probably better for an FPGA.
Note: The question mentions using the 1 MHz signal as a "reliable clock". David's answer is very efficient in detecting glitches, but most fluctuations in frequency (important if a derived clock is used to sample an analog signal), duty ratio (important or not, depending on which edges fluctuate, and which edges determine sampling instants), and most jitter (phase noise) in the 1 MHz clock will pass by, unnoticed. My answer is more complex, but detects all that.
Note 2: Response to stevenh's comment. I don't have enough space there.
What I meant was that a certain amount of logic will do the
calculation (I know it can), but that it's little use doubling the
amount of logic. It won't halve the calculation time.
Of course that increasing the amount of logic, in an FPGA, will decrease (if you are a good designer) the calculation time. That's the main reason for FPGAs to exist. Otherwise, you would just use MCUs. FPGAs are there to exploit parallelism.
Imagine A, B, C and D are all N-bit wide signals, with the same clock rate, fc. You need to compute X=(3*A+5*B)*(2*C-D), and you need to provide a new result for X every Tc=1/fc. You don't care about a little latency, as is the case 99% of the times. If you had an MCU, capable of doing one multiplication or one addition in one clock cycle Tc, you would NOT be able to generate X with the same sampling rate, fc. However, with an FPGA, clocked at the same rate, fc, you CAN. How? Exploiting parallelism.
With an FPGA, a good designer would do something like this: I don't care about having a latency of two Tc clocks. I need X to have rate fc, and it will. Just do the following. Divide the problem in 7 parts. Assign hardware to each part. All 7 parts will be calculated simultaneously. That's the key behind an FPGA. All those 7 parts will work at the same time.
Part 1: a=3*A
Part 2: b=5*B
Part 3: c=2*C
Part 4: d=-1*D
Part 5: ab=previous_a + previous_b
Part 6: cd=previous_c + previous_d
Part 7: X=previous_ab * previous_cd
As a result, you will have a new X value every Tc clock period. With a latency of 2 clock periods, but you don't care about that. So, it doesn't matter how complex the calculation is, if you can partition it into smaller sub-problems, because all sub-problems will be solved in parallel, and the time needed to do the whole calculation is not the sum of the times needed to do the sub-problems, but only the time of the sub-problem that takes the most (being more technical, is the critical path, what determines the overall performance). There is a huge difference.
So, yes. Of course that an FPGA can calculate standard deviations at full speeds! It can do many more things, at full speed.
Note 3: Now it won't even let me add comments.
Thanks for the extensive explanation. When I said "a certain amount of
logic" I meant parts 1 through 7. At a given point you can't split up
the problem any further, and you'll have to do it with that. For your
calculation of X it doesn't help to add a part 8.
For the calculation of X it doesn't help to add a part 8, and it doesn't need it. The most complex sub-problem (a multiplication) is already one that the FPGA can do in one clock cycle.
Come on! Admit it :). Your comments showed you didn't seem to be aware of that key advantage of FPGAs.