Two questions. First, what is the least amount of rounds you have taken to complete it? I almost always take decks that can outrun the Balrog. And I think I achieve that (2-player) at about third of the times. So you basically need to win on round 8 (in 2-player again) and remove no additional damage from Doom, Doom, Doom. The latter is actually not as hard as I had first thought. You just can't engage early, always choose the option of an extra card instead of removing the token, and cancel the one treachery (I mostly do with the Black Riders Frodo ability).
Now the boasting part. Yesterday, for the very first and so far only time, I won on round 7, finished Stage 1 on round 2, Stage 2 on round 4, and then three more. I have never tried Legolas who could in theory put five extra progress on Stage 3 on the round you finish Stage 2 but that is quite hard, I feel.
And the other question, and I am sorry since this must have been asked before. You remove the last damage from Doom, Doom, Doom, and at the end of that quest phase the Balrog enters play. Does he also attack at that very moment?
By the way, probably my favourite saga quest so far, together with A Knife in the Dark.