along the way is an idiomatic phrase. See below, for others.
I see no reason to get tied up in the words parenthetical or non-essential as this question is a matter of style, and, not a grammar question.
The phrase is often used.
But I would call it an adverbial phrase since it answers the question:
When did their love start to fade**?
Then, their love started to fade along the way.
It could have faded at the end, at the beginning or at some other time.
Pre-positioning the phrase is merely style and does not change how it functions in the sentence as an adverbial phrase.
No, along the way is like but not exactly the same as: without their even noticing it.
Their love started to fade without their even noticing it.
That is a prepositional phrase.