My work uses Dell servers, which have this thing called iDRAC, which is a separate embedded system that can manage the server even if the server is off. The iDRAC can turn the server on even if it's off. Even if the server is off, you can log into the iDRAC and check the status of the server and see if there are any hardware issues, see if the server is on or off, update the firmware, etc.
This sounds like overkill for a phone, but I wonder if they are doing it this way, with a separate embedded system. If they did, it could potentially use only a small fraction of the battery power Android uses. It could potentially last weeks or even months on a charge.
More likely, it's booting a separate image - not unlike recovery mode - when it turns off, and like you said, it's not actually off. But it would be interesting if it has a separate embedded system just for tracking the location even when the OS is powered down.
Ideally they'll let you turn off this feature regardless of battery implications, because it sounds like a security concern if your location can be tracked even if your phone is off.
Edit: wow, I worded my first section really poorly. But I'm to tired to fix right now. Hopefully you understand what I was saying.