Supplied with 12V AC, the DC output of your rectifier/capacitor arrangement should be about 15V or so. The 5V regulator will begin to drop out when its DC input falls below 8V, so you have plenty of opportunity to warn the Arduino that DC input is falling.
Let's say that a "safe" input potential is 12V DC or greater. We just need a circuit to produce a 5V signal when that DC level exceeds 12V, and 0V otherwise, that you can connect to a digital input. Here's how you could do that using a PNP bipolar junction transistor, with a few peripheral components, in the dotted box:
simulate this circuit – Schematic created using CircuitLab
Node IN is connected to your rectified source of DC. Zener diode D1 begins to conduct as \$V_{IN}\$ exceeds +11V, preventing Q1's base from rising beyond that limit. As \$V_{IN}\$ continues to rise to +11.7V and beyond, Q1's \$V_{BE}\$ reaches 0.7V, switching it on, and pulling PG (power good) high. D2 clamps PG to a maximum of +4.7V, to be compatible with an Arduino digital input.
Here's PG potential as DC input voltage \$V_{IN}\$ is swept from zero to +15V:
Your Arduino software, prior to writing data to the EEPROM, should check that this signal is high, indicating that DC is still at +11.7V or more. Even if AC power is gone, you still have many milliseconds before the big DC reservoir capacitor discharges to an "unsafe" level.
Alternatively, configure the Arduino input to generate an "interrupt on change", and write an interrupt service routine to quickly write encoder position to the EEPROM in the few milliseconds remaining before \$V_{OUT}\$ drops below 5V, and inhibit further writes thereafter.
This design does rely on there being not more than a couple of volts or so of ripple on the DC source, which is highly dependent on the current being drawn from it. If ripple is too significant, you'll need to increase reservoir capacitance.