Should a software license and maintenance support be on same agreement?

Although I cannot speak to whether binding those two is in your best interest, you can include language that determines the specifics of modifying or extending one or both. Whether you should is up to you, but doing so with the appropriate language will keep either from being hamstrung by the other.

I feel it depends on how profitable each sale is. If you were to sell licenses with no annual maintenance, would that still be a positive sale or do you give up some profit on the license sale to get annual maintenance?

If the license sale is a very profitable operation, I would sell maintenance as an optional add-on that could be on a separate agreement or not.

If you need the maintenance support sale you tie the two together in one agreement and maybe just give clients the option of pick a level of support so they don't feel as boxed in.

There is no legal reason to do it one way or the other. Do what works best for your business work flow.