Restarting my Mac did not help. Here is what I did:
Killed the App Store process in Activity Monitor
Long pressed Xcode and clicked X - It didn't delete Xcode, just stopped the update.
Restarted my Mac
Opened App Store, and clicked "Update"
It downloaded Xcode all over again, and started the installation again. The installation took maybe 15 minutes after downloading. I monitored progress by hovering the cursor over the rotating status circle in the App Store page - this showed a small bubble with the progress as a %age. Eventually it finished installing and the button changed to "Open".