Can I create my app on a Salesforce sandbox and upload it to the AppExchange?

No. Though you can use a sandbox to install and test your app, you must create and upload it using a Developer edition organization.