Had this exact problem on my late 2013 model Mac book pro. I tried updating in recovery mode and safe mode and it kept telling me I didn't have enough storage even though in "about this Mac" it said I had more than enough. I also tried updating over a different internet connection to no avail. After a few calls with apple support we cleared a good bit of memory (highly recommend OmniDiskSweeper to see what you're actually using) and I tried again and it still said "download failed" when It would prep the update. They recommended waiting until the next big update in September. I wasn't in a panic as this is a spare laptop. I was just about to give up and I said I would try one more time in recovery mode after clearing loads of memory and numerous other things with the support agent and finally worked. Hope this helps!