Those chords are "Flat Five Substitutions"
EX: A7 sub Ebmaj7 -- normal V is E.... FLAT FIVE is Eb.
You are basically thinking V to I or E to A or E7 to A7 or the various other extensions like 9, 11, maj7, etc.
the V by nature is a tense chord and wants to go home. Yet it is still considered "inside" or a 'normal' chord.
Jazz likes to add more tension, especially over the V chord.
So your inside notes are A B C# D E F# G# leaving A# C D# F G as the outside notes.
Enharmonically Bb C Eb F G. Bb scale = Bb C D Eb F G A compare to E7 = E G# B D
So the Bb scale adds the desired "outside" chromatic notes to your typical E7. They only share D note. the rest are chromatic additions "outside" for tension.
So if E7 = E G# B D = 1 3 5 b7
then Bb scale adds ... Bb(b5) C(#5) Eb(major7) F(b9) G(#9) to continue that the D(b7) and A(11) are diatonic to E7.
So the concept is ... play the MAJOR SCALE that is a FLAT FIVE from your FIVE chord.
You probably know that the ii chord is also the v of V,,, so FLAT FIVE is also FLAT NINE of the ONE or FLAT two made MAJOR.
Basically you play one semitone up from the ONE in MAJOR.
Again... this concept is for the V chord.
Basically what you are looking for are 'other scales' that provide you with outside notes but also have the inside notes as well and substitute them in for your strict diatonic scales that you normally use.
why they didn't call it the Flat Nine Sub... I have no idea. Probabaly because people were doing V of V substitutions already and then someone figured if they drop another half step they get all this chromatic movement which tends to work and get some cool sounding outside stuff as well.
The realization being they are only half step from diatonic home at any time.
The above is from information passed from various people and related by Danny Gatton so you can probably most easily hear it by listening to his music. He was doing it by ear and by figuring things out on paper so to speak. IOW after he was told about this half step concept he sat down and figured which scales worked with which chords. However if you research it the Jazzers will call it the Flat Five Sub.
I'm sure there is a lot more to the whole Coletrane thing but that at least explains your Emaj7 substitute for A7
You could also call on the b9 of V. In this case we have an A7 and have called on it's V(E7) but then altered it into a Flat Five of V via Bb.. V of E = B so Bb is the bV.
That's also the same as b9 of A... so either way you name it you end up at Bb scale to built that Ebmaj7.
You could also call on the b9 of E(or E7) which is F F G A Bb C D E .. .these notes fit very nicely to both E and A and have some outside notes as well. Again only 1/2 step from 'home' which would be the E chord(your expected or typical VofV for A7).
Clear as mud? ... just remember the whole point is not sound like the same old thing but to call on something new without destroying the whole deal. So you are looking for ways to add spice and hopefully be able to do so without taxing your brain..... thus "1/2 step from home".
Timing and the order you apply the notes makes all the difference more so than them being 'wrong notes'. People that know what they are doing can play all 'wrong notes' and make it sound great.
+++++++++ETA: Just to be clear the above is not to say the videos sophiehiker posted are incomplete or wrong or anything of that nature. This is simply a means to solo over whatever chords you happen to end up with. If you notice in that one video the guy says "over this chord coltrane always played such and such" He went on to say he studied many of his performances and every time he got to that chord he would call on a certain tool set or scale tones. .... same with Gatton, he might default to Bb over E7 in key of A.... The point is, you/we need something to grab on to. Let's say coltrane has this three tonic system and the notes and chords end up being the same as the flat five of five. that is the nature of music and the fact we only have 12 notes. Our job is to identify what is going on and how will we handle it in the moment.
This is basically the task everyone has. How will I deal with the chords no matter how they came to be. Some deal with them by playing "licks". some deal with them by playing a diatonic key, some deal with arpeggios, so we have two systems at play here.
How did coltrane come to play those chords. How did he decide to write his progressions. And then how will he or you improvise over them. IOW... the methods used to build the bridge will be different from the methods you use to cross the bridge.
what sophiehiker posted is how the bridge was built. what I posted is more about how you can think of the bridge so you can cross it with your guitar and the beauty of this one method is that you only need to be able to think 1/2 step from home.
Just want to be sure those two worlds are not confused. The greatest players have this ability through deep research to reduce all these complex chord changes down to simple manageable blocks.