It's unlikely that your site needs 6 minutes of CPU time to create a user but you can confirm that checking the system load during the process.
When I've faced that kind of problems the reason was one or more timeouts when trying to connect to an external service from the server.
For example, imagine that when you create the user the site querys an external database via an HTTP connection checking for the user usual nickname (Abigail → Abbie, Peter → Pete, etc). If that external service is down your site happily will launch the connection, waiting patiently the answer until the timeout is reached and connection is closed. If your site tries to connect six times and system timeut is 30 seconds then there you have your six minutes for use creation.
Check your installation for modules that may conenct to external services, check dblog for timeouts errors messages, check system log for similar messages. Disable any suspicious module and try to create a user.
If this only happens when using Services (not in the regular user creation form) narrow your search to any Services related modules or custom code.