And for the beginning of ATTYA, it's in Ab maj for bars 1-5, C maj for bars 6-8, Eb maj for bars 9-13, and G maj for the next two lines (but where does the E7#9 fit in in bar 16?)
So that covers both A sections and part of the B section. The melody is the same in A' as it is in A (just transposed to the new keys)
I think that's mostly right.
Yes, it's right. But, now look at the chords and the melody as well. It's just a sequence. When you learn tunes and analyze them, pay attention to this kind of stuff. Look at "How High the Moon" next and tell me what you notice. The E7, by the way, acts as a dominant VI chord in the key of G major and partly as a V to i because it's going to A-7 in the next measure. It's just a nice little way to get to the B section. To tell you the truth, I'm not even sure if that's in the original tune or if that's something hardcore Jazz guys did later.
Oh, and a tritone sub.... here's why it works:
The most important notes in a chord (in Jazz, at least) are the 3rd and the 7th, which are called 'guide tones.' The 3rd because it determines whether it's major or minor (or diminished) and the 7th because it determines whether it's a major, minor, dominant, half diminished, fully diminished, etc. 7th chord.
So, if you have a basic C7 chord: C-E-G-Bb
You could actually take away the C because you don't need it (bass handles roots most of the time), the 5th isn't important unless it's altered. That leaves the 3rd and the 7th, which define the chord for the reasons I specified above.
Now, let's say you go up a tritone from C7, which would be Gb7 (or F#7). A tritone is simply an augmented 4th or diminished 5th. Just another way to say it. The reason Gb7 works as a substitution for C7 is because the notes of Gb7 are:
Gb-
Bb--Db-
FbC-
E-G-
Bb If you notice, the guide tones of each chord are the same, just reversed (bolded above). So, you still have E and Bb as the guide tones, which is why you can use Gb7 in place of C7, because the guide tones are the important notes, anyway.
But, what about the other notes in the Gb7 chord? How do they work? The Gb is a flat 5 over the C7 (or a raised 11th, however you want to think of it) and the Db is a flatted 9th. So, basically, if you play a Gb7 chord in place of a C7, you're still getting the 3rd and 7th of C7 (remember, it's the same two notes in both chords), but now you're getting a couple of tensions as well. It's an easy way to bring the harmony 'outside' a little.