Another thing to consider - I noticed that, even after unpairing and setting up my Series 3 as a new watch, I would start with > 3Gb available, only to have the upgrade consistently fail. The upgrade reason was strange - “the upgrade cannot be verified because your Apple Watch is not connected to the internet”, even though it was. After this happened a number of times, trying different combinations of Bluetooth and WiFi on/off, I noticed that I had zero memory on the watch, and that my Music app had expanded to 1.5 Gb. That’s when I noticed a setting on my iPhone watch app “Music->Recent Music” which automatically adds new music to your watch. This must be a default setting, because I don’t ever remember checking this and never set up any playlists to download to my watch. So, it appeared my iPhone was slowly adding music to my watch during the upgrade, until the watch ran out of memory!
Long and short - when I turned off this setting, the 3Gb I had recovered from pairing and setting up as a new watch remained available and the install of WatchOS 7 (7.2 in my case) was successful. Quite the road to get there, though!
