Are you connecting to Gmail using IMAP both on the iPhone and on the Mac?
With IMAP, devices try to show you mail as it exists on the mail server (e.g., Google's mail servers). This is useful for synchronizing mail across devices.
With POP, devices make permanent local copies of mail (and may also delete mail on the server). If your Mac was set up to use POP, deleting mail on the iPhone would not delete mail that the Mac had pulled down to its local Mail foders, even if the iPhone itself had an IMAP connection.
You probably have IMAP connections from both the iPhone and the Mac, but I thought I'd throw this out there.