Despite the fact the interest rates are so high, payday loans are not a very profitable business. The reason the interest rates are so high is because they are rarely paid (expectedly). Most of the payday loan companies in the US have profit margins on 6%. Compare that to legitimate banks who have 30-40% margins. Any tighter restrictions would wipe away what little margins they have.
Chances are if you did regulate them, it would be same as outlawing them. Legitimate businesses wouldn't be able to keep the lights on, leaving the entire business once again to criminals.