You could have two Template Variables called "previous" and "next" and just put the document ID of the previous and next docs in them. Then this code in your template would provide links to them:
<a href = "[~[*previous*]~]">Previous</a>
<a href = "[~[*next*]~]">Next</a>
It’s not nearly as slick as what you have in mind, but would definitely work if you can’t find a better solution. Later, you could adapt them by using @eval in those TVs with code to find the previous and next docs by menu index.
[Update] After checking it out, OpenGeek’s snippet looks like a better solution. You could alter it to remove the "direct" and "template" modes since all you want is the URLs.