While I've never used AdWords for getting SEO clients, I've had a lot of success with AdWords for various lead generation websites in tons of different industries so I don't see how SEO would be much different. I will say that there is probably a ton of competition for SEO related keywords on AdWords so I have the following suggestions:
1. Start out with a tiny budget, like 5-10 bucks a day, and gradually expand as you figure out what works.
2. Use the AdWords Keyword Tool to find [exact match] keyword phrases with low competition and low CPCs. Don't worry about going after the most popular keyword phrases as they are more likely to be more expensive and less targeted.
3. I'd also suggest starting out by targeting only a specific geographical area. So if you live in Chicago, only target users who are searching for your keywords that live in Chicago.
4. Use only the Google Network to start off, so turn off Search and Display Networks.
5. Include your targeted keywords in the ad copy, ideally in the headline. So if I searched for "SEO Company Chicago" then that should be your ad headline since it will be bolded and catch my eye.
6. Send AdWords traffic directly to a dedicated landing page, ideally with the exact match keyword as the headline on the page. You can do this with dynamic keyword insertion and a little bit of scripting. Add a clear call-to-action and/or a contact form to make it as easy as possible for users to contact you directly. Also, if you can offer something for free, such as a "Free SEO Audit" then I definitely suggest offering that.
7. Follow up immediately on your leads! A fresh lead has a significantly higher chance of converting into a client versus one that is a few days old.
Hope that helps!