When and how did the phrase "Aliyyun waliyullah" originate? Is it a part of the Shahada? Is it a part of the Tashahhud during prayers?
as salam alaikum
the phrase "Aliyyun waliyullah" can be explained in the light the following Qur'anic verse: "Behold! The awliya' of Allah neither fear shall overwhelm them, nor shall they remain in grief" (10:62). A faithful person who have sincerely studied the life of Ali, peace be upon him, will find no problem to count him among the most outstanding examples of those awliya' mentioned in the ayah.
The above-mentioned sentence however is not a part of the tashahhud that can be said during prayers and we don't have any authentic chain of transmission to validate such claim. The salat is an act of worship and we should not add any wording to Islamic worship that has not been prescribed by the Almighty. The believer should be satisfied with what Allah has given him and avoid to exceed His boundaries.
Furthermore, among the acts which invalidates the salat is to speak while praying, unless we are pronouncing Qur'anic verses or specific du'as (like in the case of qunut). The phrase is not as such, rather it is a testimony (which many Shia Muslims add verbally to their shahadah) and an acknowledgement of faith: therefore it is considered "additional talk".
It is necessary in this regard to stick to what has been transmitted to us via mutawatir chains of transmission or, at least, through authenticated reports.
With prayers for your success.