In most Ashkenazi versions of the selichot* for Elul and Yomim Noraim, the day's selichot begin with Ashrei**. This seems rather weird, especially considering that some (including Jekkisch authorities and the Gr"A) consider the recitation of Baruch Sheamar to be a berachah on reciting tehillim.
What is the earliest source for the recitation of Ashrei at the beginning of Ashkenazi selichot and what other versions, such as beginning with Adon 'Olam are attested to in Rishonim ?
*Versions consulted were the Minhag Russia (Chaba"d), Polin and Lita (Artscroll), and Anglia (Rosenfeld/Judaica Press).
**In my own rite, the Frankfurter minhog, we begin with Adon 'Olam, see R' Shimon Schuster's edition here.