Yeah, I got the UD epic mount for my shaman 'bout a year ago, it was a complete pain. Hadn't done much quests that gave UC rep, so mostly had to buy/grind Runecloth all the way. Can't remember exactly anymore, but probably spent over 700g on the Runecloth since I was too lazy to grind it most of the times.

If you want a cross faction mount, it'd be wise to plan it from lvl 1, ie. go and do quest at that faction's starting area, and later in the leveling do as much quests you can that give reputation with the faction. It helps, a lot.

I'm planning to get the green Undead epic mount for my
paladin when she reaches 60. lvl 53, and already revered, halfway through to exalted. I don't really understand how I pulled it off, but I sure am happy for it. ^^ I do recall that I did the quests at Brill, and most likely the quests at Silverpine after that, but can't imagine that alone being enough. :p