I'm applying to PhD programs and want to ask for a reference letter from my former supervisor, who has since moved to a new university, so that his old work email is not working anymore. I've been asking him through his personal email; however, as he rarely checks it, sometime it takes more than a month for him to reply to me. One of the universities to which I'm applying has a deadline coming up in less than a month and I haven't heard from my former supervisor for a while. While panicking, I searched on Google and found his new email address. I wonder if it's reasonable to send email to that address and remind him as he never gave me the address.
From the formulation of your question, to me it seems your main concern is if it is polite to send an e-mail to the address you were never explicitly given, but instead found it on your own Googling.
It looks like you found his/her new work address. If that's the case, I'd say it's completely fine to send an e-mail. All the right reasons for contacting your former adviser before the deadline are already mentioned in @aeismail's answer.
I'd just like to add that I've been told over and over again that a good letter of recommendation from your former adviser is expected, and that it's extra great if you can have letters of recommendation from more than one of your former advisers: those are the people who were supposed to be working closest with you and who continually assessed your progress over a period of time. If you can't get them to say something good for you, you must be very very special in some other way to get accepted to a PhD.
Back to the is it polite point: it is a work e-mail you found. That's the way he's expecting to be contacted concerning scientific things. It's public and accessible to everybody. That does not mean he'll reply to everything, but if you're one of his former students, he should be glad to reply if you split on good terms.
Also, I've contacted everybody who gave me a letter of recommendation after I got my PhD grant, and I sad "thank you". I went to visit my supervisor in his office for a few minutes before I moved away for my PhD: those people, and he especially, are who made me love science, and made me look for a PhD in the first place. He often said that advising students on how to go further with science/research was one of the best parts of his job. So, maybe I was just lucky, but in my experience, your former advisers will be glad to help you, glad to know their help mattered and won't mind you contacting them.
Yes, it is a good idea for you to contact your old advisor about the upcoming deadline, particularly if he normally takes a long time to get back to you.
Advisors are busy people, and have a lot of different tasks to complete. Sometimes we need a reminder that things are due, and a well-written note that politely asks us to take care of something is usually very welcome. A "bossy" or impolite note, however, will not help you and should definitely be avoided.