I work with accelerometer chips, a lot of them have features specifically for pedometers. Keeping the accelerometer on will draw a few uA, then you can have the accelerometer keep track of the step count internally and have the main processor query it as necessary to update the step count display. When there's no motion for a while, you can also put it into a lower power sleep mode that doesn't track steps, then when it detects motion it'll wake up the main processor which will then put the accelerometer back into pedometer mode. I think 2 years on a CR2016 (90 mAh) is reasonable if Casio knows what they're doing.

If it's like the G-Shock, it's not a real step counter, it's a small accelerometer. It will trigger on every single wave when you're planing if you're windsurfing, which makes it quite useless.