Update: Apple has given a statement on the issue that caused the iOS 10 update to fail over the air, and says it has now been fixed.

“We experienced a brief issue with the software update process, affecting a small number of users during the first hour of availability. The problem was quickly resolved and we apologize to those customers. Anyone who was affected should connect to iTunes to complete the update or contact AppleCare for help.