I had this problem just last night - iPhone 6 stuck at verifying update, then stuck at verifying restore when I tried that. Multiple attempts to shut down, reboot, cold start, etc. ... nothing worked. Rebooted the iMac, tried everything again, still no luck.
I plugged the phone into my MacBook instead, and repeated. Again, could not verify the update, but - Ta-da! - I was able to restore the phone from the backup on the second attempt. (I was already looking at replacements on eBay when the progress bar on the phone suddenly started to move.)
Take home lesson is, don't give up too easily. Try another Mac, or even a PC with iTunes installed. I think the problem is a bad download of the update to the Mac, which bricks the phone and makes updating impossible. At least in my case, persistence paid off.