From his earliest convo with Cotillion in tBH we know Edgewalker is, or was, an elemental force/elder. His technical name appears to be Tracer of Edges. Kind of tough to pin what he is, since the few times he's been active it's mostly been by getting people the hell out of Shadow (ousting ornery beings from RotCG, repelling the "alien" Riders and denying Jhenna entrance to Shadow in NoK, etc). At this point he's basically the old guy that yells at kids to get off his lawn. The following are a few relevant quotes about his relationship to Shadow and things that may hint at his nature.
Re: Edgewalker said:
'I cannot say the same of you, Cotillion. I walk--'
'Yes, I know,' Cotillion cut in, 'you walk paths unseen.'
'By you. The Hounds do not share your failing.'
Cotillion frowned at the creature, then glanced back, to see Baran thirty paces back, keeping its distance. Massive head low to the ground, eyes glowing bruised crimson. 'You are being stalked.'
'It amuses them, I imagine.' --TBH p.47
'I do not take your orders.'
'Perhaps I should summon the Hounds to tear you limb from limb.'
'They would not do so.'
'Truly? Why?'
'Because we are all kin. Slaves to Shadow.'
'Ah, I see. You have been taken by Shadow. You are a slave to the House.' -- Edgewalker and Shadowthrone, NoK. p286
'You can read my thoughts?'
'I possess no such omniscience. Although to one such as you, it might appear so. But I have existed ages beyond your reckoning, Cotillion. All patterns are known to me, for they have been played out countless times before. Given what approaches us all, it was not hard to predict.' --TBH p.49
'You have called me here to . . . mitigate.'
'I have.'
'This has been a long time in coming.'
'You might think that way, Edgewalker.' --Hood and Edgewalker, TtH p.3
Now I'm going to provide some quotes about the Errant, Master of the Tiles, the Walker Among the Holds (RG p.239), yadda yadda. We know he is the earlier counterpart to Paran, Master of the Deck, the Wanderer Within the Sword.
Re: The Errant said:
Edging askew the course of the fates -- I was once far more. Master of the Tiles. All that power in those scribed images, the near-words from a time when no written words existed. They would have starved without my blessing. Withered. --RG p.300
When Paran speculated on the cause of Draconus' wagon in MoI he observed: 'Before Houses there were Holds. Both fixed, both stationary. Settled. Before settlement . . . there was wandering.' (MoI p.174) The Houses and the Holds both have a master. What about the forces that came before, before even language?
Edgewalker is now apparently a servant of Shadow, which implies that isn't his original aspect -- NoK indicates he's been trapped by it. The seems like a ways to fall for a Master of . . . whatever . . . but it's not beyond the realm of possibility. The Errant, though confined to Letheras by the events of the series, was present for the collapse of the First Empire and engaged the Forkul Assail in war before his power diminished, leaving him with an ever-dwindling sphere of influence. Gods don't age well, apparently.
Though the jury's still out on Paran, both Edgewalker and the Errant are familiar with patterns. While that in itself doesn't necessarily mean much, as it could be just a sign that Edgewalker is a crotchety old man who's seen it all before, it was kind of interesting Hood invited him to the meeting where, presumably, he planned his own death to "mitigate" circumstance. And, from what we've seen, the primary purpose of the respective Masters is to sanction or deny Houses, Holds, and Unaligneds. It might make sense to have someone with that sort of experience involved in the death of the Lord of Death -- death being a concept old enough that we've seen (I think) Eres holy places devoted to gathering it. The ensuing power vacuum could have gotten messy. He was also present the night Cotillion and Shadowthrone ascended and took control of Shadow, and noted it was far from the first change-over he'd ever witnessed. While he calls Cotillion a usurper, he seems to sanction their presence.
There's also the title Tracer of Edges. Later in tBH Cotillion speculates about "lost elementals" -- stuff like time, silence, sound, etc., and all the problematic bleed between them. It's possible that Edgewalker's capacity was to define boundaries between these elements, some of which later included realms. The Tiles and the Deck seem always to need an unaligned guiding hand. If something came before, it seems likely the same rules would attach.
Disclaimer: I'm in a slow, non-linear reread of the books, and as such I have massive memory gaps despite the ability to pull gratuitous quotes. Feel free to point out hillarious inaccuracies.