Referring created users to 'admins' that created them
Add a field (e.g. created_by) to the user profile by going to /admin/config/people/accounts/fields.

Then implement hook_user_insert to populate the field whenever a new user is added.

hook_user_insert is called after "A user account was created." 
So both $edit->uid and $account->uid have the user id present.

If you changed any values in either of these objects you would need to call user_save in order to save your changes.

An alternative to avoid calling user_save again, just after the initial user object has been saved would be to use hook_user_presave that is called when "A user account is about to be created or updated"

The description of hook_user_presave goes on to say:

This hook is primarily intended for modules that want to store properties in the serialized {users}.data column, which is automatically loaded whenever a user account object is loaded, modules may add to $edit['data'] in order to have their data serialized on save.

So another option here would be instead of creating a new field (with a new table), this information could just be stored as a serialized array in the data column of the user table.

This would mean it would be slower to search for users created by a certain admin, but would would have less storage overheads.