Garmin Express sucks. While it works most of the time for its normal software functions, the really critical stuff such as firmware updates don’t work well.
I had to hunt for the GUPDATE file for my Garmin Edge 810 and install it manually.

I finally managed to find the file located at Garmin firmware files.

Just download the appropriate file and copy the GUPDATE into the /GARMIN directory of your device’s main memory. Unmount and Reboot the Garmin and you should see the file getting picked up and installed. The device might reboot a couple of times and finally, it should settle on the normal use screen.

I had to re-pair my iPhone in order to use the Garmin Mobile Connect app again. Language and certain metrics had to be re-set up too. But once its done, everything works fine.