How do I allow another user to create new users?

Put a user in a Role which is set to basic access with sharing

Just to be clear, I'm talking about adding users to the account. We have two users with Full management levels but neither had the "Add User" button available.
So then created a group and added them as Manager/Member to see if they could add users but alas, there wasn't an option either. 

When you say "Full Management Levels" that sounds like the Realm (account) level access. That does not give them any access to the actual app.

In the Roles for the app, you will need to create a Role for these special users, typically by copying the Participant Role and then set the checkbox for the Permissions tab for that Role to be

Manage users and share the app

The wording of that option has changed over the years so my initial wording in this thread to look for has changed.

I'm talking about adding users to our account not users to an app (that's easy).  So yes, realm.

I�m not sure about that, but I typically don�t add users that way. I just invite them to the app and they will become Users listed in your Realm.

How do they get assigned seats if they aren't added to the account? 

Ok. I'll try it. 

The account realm is responsible for paying for any users which have access to any apps. You can invite your dog walker to the app and boom you are now playing a license fee for that dog walker.