Possible solution
After checking I see that Turian is correct.
Maybe some people would appreciate knowing exactly what settings google recommends, and why. So here is the link to that info:
http://mail.google.com/support/bin/answer.py?answer=78892
Click on the Apple Mail link on that page and use those settings. The explanations at the bottom of the page tell you basically what happens.
But there is hope.
Here is a solution that worked in my limited testing (but I do not have anywhere near 13000 messages in my gmail account).
1. Set up Mail with the recommended settings.
2. Login to gmail from your browser.
3. Click on "Settings" at the top right of the window.
4. Click on "Labs". (Hopefully this is available for you, it is not on the screenshot from Turian, but is is for me.)
5. Read the info at the top of the screen, then find "Advanced IMAP Controls" and click "Enable". Make sure you also click the "Save Changes" button. (See screenshot)
6. Click on "Labels".
7. Remove the "Show in IMAP" check mark for "All Mail". Remove the check marks for all other labels you are using unless you want those messages to be on your computer. (See screenshot)
8. If Mail is still running you may need to quit and relaunch it before the changes are made. (Might take a little extra time the first launch as it decides what should and should not be on your computer.)
Now you only have a limited number of messages on your computer and all of them are still on the server. Bobs your uncle.
