Is it possible to track/save Google searches that were never submitted?

As inefficient as it sounds, that's exactly how it works.

Head on over to google.com, bring up your developer tools in your browser (CTRL+SHIFT+I or CTRL+OPTION+I in Chrome), click the network tab, and then start typing in the search box. You'll see a series of GET requests to to the /complete/search url path, like this:

https://www.google.com/complete/search?client=psy-ab&q=he
https://www.google.com/complete/search?client=psy-ab&q=hel
https://www.google.com/complete/search?client=psy-ab&q=hell
https://www.google.com/complete/search?client=psy-ab&q=hello

You'll probably have a bunch of other query parameters in there, but the client identifier and the query are the two required ones. The return from that request contains the autocomplete list for the substring you typed.

This means that autocomplete queries follow the same storage rules as not-autocomplete queries; if you have a proxy or cache or whatever, they'd appear there.

There's a couple of special rules at play, though: since they're XHR queries sent in the background rather than queries you type into the URL bar, the browser doesn't put them in your navigation history. And (IIRC) Google only uses this feature if you're on TLS, so it won't ever send these queries over plain text. And finally, since Google knows that they're autocomplete requests instead of actual searches, they don't appear in your stored search history associated with your account.

In terms of efficiency, this is why Google is investing so much in protocols like SPDY and QUIC (variations of which are now being standardized as HTTP/2 and HTTP/3). These allow extremely low-overhead HTTP traffic, getting it down to as low as one UDP packet in each direction for one of these autocomplete requests.