I need to check if the new software has been generated by a "trusted"
source, ie me.
This means you need a single key - your key. You embed your public key into each device. When later on you upload an update to each device, you sign the upload package with your private key. Each device verifies your signature using your public key that you have embedded into the device.
If my private key is lost for whatever reason, I lose the ability to
update any of these devices.
Correct. I would suggest you to proceed like CAs do. Often the end-consumer certificates are issued not by the "top level" CA, but by some "intermediate" CA.
So you can create a "top level" key pair and corresponding certificate, and embed public key (or certificate) into each device. You should keep this private key in a very secure place.
Then let say every 3 months you do following: You generate a new intermediate key pair, create a certificate which expires in 3 months. You sign this certificate with the top level key. You use this intermediate private key to sign any updates in the next 3 months.
Since you want to sign 1M units, it may happen that you lose the private key. In such case you just generate a new intermediate key pair (without waiting 3 months), sign it with the top level key, and use this new intermediate key to sign updates from now on.
Each device should verify the packages as follows:
Check if signature matches the certificate attached to the update.
Check that certificate is issued by the top level key, which is embedded into device.
Check certificate expiration date.
Of course, if you lose the top level key, you will be blocked. But since the top level key will be used rarely and kept much more securely than a key used for 1M signatures, the chance to lose it essentially lower.
I'd suggest that you consider also revocation of the keys. It can be needed if a key used to sign updates is stolen, or if you just suppose it is stolen. You may want to prevent the attacker from uploading malicious updates signed with your stolen private key. In such case you can have a CRL (certificate revocation list) on each device. In case you want to declare some key as untrusted, you generate certificate revocation info for the compromised key and push to all devices. Then generate a new intermediate key pair. In case the device obtains a package signed by a stolen key and finds this key in its CRL list, it should not trust such signature and should reject such update package.