not enough internal memory for software update

so, I hit the following catch 22 situation:

When trying to update the device software on my edge 840 via Garmin Express I get the error message, that the device has not enough internal memory.

Based on the suggestions I tried to use the map manager and get rid of the not needed maps, e.g. NA and Trails.

HOWEVER, when I try to do this, Express tells me, a software upgrade is needed first, before I can use the map manager and stops the process.

This puts me back to square 1.

According OSX Finder, the edge has 3 MB free space left on the device.