Yeah, that second is how we'd do it: create a work (after double-checking that one doesn't already exist), link it to the original recording, and link the same work to the cover -- being sure to check the "cover" box on the relationship. We'd only create a second work for the cover if Tessa Violet significantly changed things.
The idea behind that is to handle situations where the original artist recorded multiple versions of the work. We can't always figure out which version would have been the inspiration/basis and that's assuming that it can be traced back to a single version. Linking to a recording means that we would need to figure out that single base, while linking to a work allows the full range of potential recordings. It's not quite that simple, but it works as far as your question is concerned.