Tiny Magnet Sensor Switch
Your idea to use a Hall Effect device would seem to be ideal.   

There are plenty of Hall Effect sensors, here is one at about $0.40 that would be ideal IMO. It operates at 2.3 - 5V and has an open drain output and so could be used with a single digital input with just a high value pullup resistor. You could probably even just use the inbuilt pullup supplied on most MCUs (in the 20-50k Ohm range. 
You could search for others on Digikey.  

It has ultra low power consumption, but you could drive it using a digital output pin, so it's only turned on when you want. I assume to get very low current consumption of your MCU you are spending most of your time in sleep mode. Before you go to sleep simply turn the port supplying power to an input (lowest power consumption) with no pullup resistor.