The enemy has already committed to a destination square by the time the fighter interrupts their shift. The enemy cannot pick after the immediate interrupt has occurred.
There's two things to consider here: the first is when a shift occurs, and the other is when an immediate interrupt occurs within that shift.
When does a shift occur?
A shift doesn't occur the moment you say "I shift." It's a movement action, and so a shift only occurs once you move from one square to another. No shift occurs until the enemy begins shifting into another square, and once they're shifting into that square, they can't just change their mind about which square they're shifting into, and the square it's shifting into is known to all.
Besides, if the fighter's attack responds to the enemy shifting, how can you possibly react to a shift which hasn't begun happening yet?
When does an immediate interrupt occur?
It occurs at no specific point during the action, and really, it can occur anytime during it. From the DDI Compendium:
Interrupts: An immediate interrupt jumps in when its trigger occurs, taking place before the trigger finishes. If an interrupt invalidates a triggering action, the triggering action is lost.
Example: An enemy makes a melee attack against Keira the rogue, but Keira uses a power that lets her shift away as an immediate interrupt. If the enemy can no longer reach her, its attack action is lost. Similarly, Albanon the wizard might use shield in response to being hit and turn that hit into a miss, or Keira might use the immediate interrupt heroic escape to evade an enemy’s attack before it can deal damage.
It's best to think of immediate interrupts this way: the action plays out completely as normal (including that the shift occurs in its entirety). However, something happens at some indeterminate point in the middle of it. When that something occurs exactly is not specified anywhere; this is a matter that is of no concern to the mechanics and is only a concern to roleplaying. That something may have an effect on the outcome, including causing part of or all of the action to never have happened.
