I'd say mechanics every time. Prototype it right now. The core game has to be fun and responsive.
But it's not just about the action parts, the UI must be smooth and satisfying too. Once you get that right, the story can be slotted in easily.
Here is a great blog post about priorities in game development.