DOORS (Dynamic Object-Oriented Requirements System) is a requirements database tool specifically designed to manage requirement specifications. It is sold by IBM (by Telelogic before they were bought by IBM) and is heavily used in the US defense industry (and often even contractually mandated).
A little background on how DOORS works is instructive in understanding how it might be used to link to user stories:
- The requirements from a given specification reside in a single module, with each requirement and it's associated meta-data stored in a separate object.
- A group of modules thus form the set of specifications for a complicated system such as a satellite--starting at the top-level Prime Item Development Specification (PIDS) and flowing down through the lower-level specifications all the way to Software Requirement Specs (SRS) and the hardware equivalents.
- The inter-relationship between requirements at these various levels is documented and managed with links. Links are connections between requirements (i.e. objects) that (typically) reside in different specifications (i.e. modeules).
Links are how you're going to map your mercurial specification to your backlog.
Links show parent-child requirement relationships. In your case, it appears as if you've received a spec from your customer and want to be able to trace the user stories to their requirements. Assuming that your user stories actually have a fairly straightforward mapping to parent requirements this should be easy to do. Each user story can be an object in a story module that links to a requirement.
These links are then used during the design and development process to understand how requirement changes at one level of the hierarchy flow through the entire system.
For example, if a high-level performance requirement is changed, a simple report run on a properly linked set of specifications will enable the systems engineers to determine the comprehensive set of child requirements that now have to be assessed for impact. Or in your case, a requirements change can be instantly traced to the user story(ies) the change will impact.
DOORS will then enable you to run audits to see if there are any requirements not mapped to a user story, any user stories not linked to a requirement, and any other combination you can think of (e.g. requirements satisfied by several user stories, although this probably indicates the requirement is insufficiently decomposed).
Once the code is complete and released, the meta-data for the user story and spec can be updated to show the requirement has been satisfied and reports generated to show overall progress and outstanding features.
I'm sure there are other tools (probably less expensive ones) that have similar functionality, but DOORS is by far the most ubiquitous--at least in the aerospace and defense industry.