Power Fail Monitor and ADC measurement
Since you are already regularly sampling the input voltage, you don't need any more hardware.  The information about the input voltage is already available to the firmware as things are now.

You do have to sample the input voltage "often enough".  Every 1 ms (1 kHz rate) is probably plenty fast enough.  That's a rather slow rate to run the A/D at, so should not represent much burden.  Each sample, compare the new value to some minimum threshold.  If it is below this threshold, then set a flag or whatever you do so that the shutdown sequence is eventually run.  Since you probably have 10s of ms of time at least before power is lost, sampling every 1 ms should be good enough.