UPDATE* Tried safe mode, no luck. Tried changing wifi from router to iPhone link (as another user suggested worked for them) and no luck...same stupid lying message about checking my internet connection.
Same issue- brand new iMac with the M1 chip and out of the box storage available (like +800G) and high speed internet. Says 2-4 days to download 12GB and fails. Not sure what the deal is but on second try now (2 days) and will call store if it still doesn't work or there's no good answer here. Sort of underwhelmed by this issue given my expectations for Apple.
This sort of problem arises, when the System Analyser had less knowledge of about third-world countries and IT system in those countries. Such stupids are mostly from rich family, from USA or UK, studied in Harvard or similar rich Universities and then joined Apple or Microsoft. In recent years, Windows also following path of macOS, and setting lots of obstacle for users worldwide.
I had this issue with my MacBook Pro (Intel). I took it to the Apple Store and they somehow managed to install the update. Then the issue popped up on my iMac (Intel). After trying all the steps outlined in this and other forums (recovery mode, etc), I finally figured out that I needed to boot off of a separate drive to install the update. I created a bootable USB drive using the instructions here: https://support.apple.com/en-us/HT201372.
Once I booted from that drive, the install went flawlessly.
Good luck.