A coulomb is defined as the amount of charge, or the number of electrons, that passes by in one second, when a current of one amp is flowing. It's a lot easier to think of a coulomb as an amp-second than it is to think of a gazillion electrons.

For a capacitor, C = Q/V, where C is in farads, Q is in the charge on the capacitor in coulombs, or amp-seconds, and V is the voltage across it in volts. That equations rewrites to CV = Q.

Using this equation twice - at the moment power fails, and at the end of the delay:

CV_{i} = Q_{i}, and

CV_{f} = Q_{f},

where "i" and "f" designate initial and final values. Subtract these equations, and get

C(V_{i} - V_{f}) = (Q_{i} - Q_{f})

The right-hand side,(Q_{i} - Q_{f}), is the change in charge on the capacitor: the discharge current multiplied by the duration. Solving for C,

C = (Q_{i} - Q_{f}) / (V_{i} - V_{f})

and substituting to eliminate the troublesome charge,

C = iT/deltaV, where i = current, T = duration, and, deltaV = change in voltage.

Our assumption is that the discharge current is constant. This result isn't applicable when the load is, say, a resistor.

You don't say whether power is cut off unexpectedly, or whether it cuts off under human control. If it's under control, you could just tell the Arduino to turn itself off via a digital input, and let it open a solid-state switch when it's ready to shut down, and use a regular-sized capacitor.