How does QA verify that existing product functionality is still working while verifying new product features and functionality?
Regression Testing. Partly automated, partly manual, depending on the tools, time and money.
Normally you should different levels of testing, and even though as software developers we would like to automate everything, some things have to be verified by hand, by having a collection of test cases executed by testers.
The Wikipedia article on regression testing is a good read.
From the whole collection of tests that most be checked by hand, it is normally worthwhile to select the minimum set that guarantee the functionality of the system to reduce costs. The balance, of course, is a fine one and depends a lot on how much the code was actually changed. Good modularization of the software product helps a lot on having good regression testing.