I'll suppose you've already activated POP & SMTP support at your Gmail account.
Have you tried using a different server? Maybe "Too many login failures" means you tried way too many times to login using incorrect credentials and they've banned your server's IP for a while.
Every time I've installed and used WHMCS has been using the local mailserver. And I had no problems at all - I don't see where do you see the difficulty on using your own server's email.