I tried @Beem335i's method but wasn't successful on my iphone XS Max with a series 2 watch.
However, after a couple of hours - I found my personal hotspot was On on my iphone - I turned it off and tried again to update and it was successful. Probably the watch using Bluetooth to communicate with the iphone messes things up and conflicts with the hotspot...worth for the iOS and watchOS developers to look at.