What is your overall power architecture like?
A typical scenario is: higher voltage input (say 12V), 3.3V logic supply. You can use a series diode to prevent the 12V supply from discharging through the source when it gets turned off. That leaves your device on its own as voltage drops.
Say you need 5ms hold-up time to write EEPROM or whatever and verify shutdown. If your load draws say 10mA, and the regulator drops out at 4V, then you have 12 - 4 = 8V of working room. If it's a linear regulator, then the 10mA is drawn from the input capacitor, and I = C * dV/dt holds. Solving for C, we need 6uF minimum. If it's a switching regulator, more energy from the capacitor is used, and the value can be smaller (in practice, it may be enough just from the input noise filter alone).
Calculator:
https://www.seventransistorlabs.com/Calc/PSHoldUp.htmlIf you need more current, or more time, you need proportionally more capacitance. It can get intensive, quite quickly!
As for detecting shutdown -- why not simply wire a voltage divider from +12V to an ADC input? Or a comparator, if you have a logic rather than analog input handy. That way, you detect power failing,
long before VCC itself is affected.
If you don't have a high voltage input, your options are much more limited. It may be worth using a wide-input switching regulator (SEPIC, say) to give you that much needed breathing room. If you're doing it by VCC voltage alone, then you have perhaps a fraction of a volt (say 3.6V nominal, 2.7V shutdown: only 0.9V operating range!) in which to detect the panic condition, and do something about it. Yes, you can brute-force it with ever larger capacitors, but it's usually the case that you can find other excuses to "do it right".
Tim