I completed the Google interview process and got an offer for an internship a month or two ago, and it sounds like how you're currently feeling is almost identical to how I was feeling.
I got the same document you did (red-black/AVL trees, dynamic programming, discrete math, graphs), and my skillset was about the same as yours. I'm pretty familiar with all the typical data structures but pretty much started panicking when I saw that list -- I had no idea how to actually go about implementing a red-black tree, for example. I also found a copy of Cracking the Coding Interview, started panic-reading it, etc...
As it turns out, my interviewers didn't touch on any of those.
My first two interviews were on-campus and lasted about an hour each.
My first interviewer was really friendly -- he asked me about some of my projects, and we spent about 10 minutes talking about it. I happened to be working on one of my projects shortly before the interview started, and so was able to briefly demo it to him + show him a presentation about it, and he seemed pretty impressed. I mentioned that I was trying to implementing something on it related to databases and he suddenly got excited -- apparently, he had just read an article about a library which would be perfect for what I was trying to do, so we spent like 2-3 minutes trying to google and find this library again (we eventually found it).
My first actual question was a pretty easy string-processing question. I got the feeling it was a sort of "warmup" question designed to make sure I actually could program. I solved it pretty quickly, then he mutated it to a design question. He asked me what I would do if the amount of data that I needed to handle suddenly increased by a huge amount and how I would adapt to code, and eventually had me solve that.
As best as I could tell, this question ended up testing me on my knowledge of basic data structures (hashmaps, lists, strings), program design, and overall architectural design.
I was then told to implement a data structure (with some constraints/unusual quirks. It had to be thread-safe, for example). That wasn't too difficult either, though I did have to frequently go back to fix edge cases he kept bringing up.
To be honest, I think I came up with a slightly easier solution then he expected -- I think he was expecting something involving linked lists or something, but I found a solution involving a fixed size array and some fudging around with indices.
My second interview didn't go as smoothly. Unlike my first interviewer, who was pretty engaging and would go back and forth with me, my second interviewer pretty much just told me the problem statement and told me to "solve it on the whiteboard".
My first question was a tree problem. I sort of awkwardly started whiteboarding and talking through what I was saying while he sat in the back in silence, and ended up finishing. He did give a few hints here and there, and asked me to come up with test cases, so I spent like another 5 minutes just coming up with tests.
As it turns out, I completely messed up this problem, and didn't see it until after the interview -- I missed a huge case entirely. I think prepping a little more for specifically tree-related problems/some dynamic programming-related things might have benefited me here.
He was the most nitpicky interviewer I've ever had -- normally, most of my interviewers seemed ok with me eliding out uninteresting or repeated bits of code, but it almost felt like this interviewer wanted fully syntactically correct code.
The second question was a design problem. This also didn't go as smoothly -- I misinterpreted his problem statement, so I spent like 10 minutes trying to understanding the hints he was giving and adapting to a subtly differently different scenario then the one he had in mind.
Protip: the word "store" is ambiguous -- it can mean either a physical store, where you buy things, or a datastore, like a database.
After that point, I moved on to the host-matching process, which was pretty straightforward. I wasn't really asked any technical questions (except for one interviewer, who asked me how I might implement Google's instant search) -- they mainly focused on things in my resume.
Interestingly, all of my interviewers during this phase were working on projects that involved Angular.js, and called me specifically because I had also worked with it before at my last internship. I think this was the first time I've had a company interested in me due to a specific technology I've worked with, which was a novelty.
So, all in all, most of the things I was panicking about didn't turn out to be relevant. I definitely did need a strong understanding of the core data structures and their big-O runtimes, and I definitely should have studied more tree-related problems and algorithms and perhaps some more dynamic programming, but I definitely didn't need to know anything about self-balancing trees or discrete math. I'm not sure about graphs. I got the feeling that the fact that I wasn't asked any graph-related questions was more of a coincidence then anything.
As for sorting -- just memorize how to implement quicksort and mergesort, and if anybody asks you which sorting algorithm is best, toss out those two/their differences, and briefly mention Timsort.