I've been corresponding with NLM about this issue and I finally took the time to try out their suggestion (which personally I found hard to see between the lines and which is not a discrete solution, but rather a very time-consuming manual process containing false positives because they say that to get a formal and comprehensive response to my query:
Collecting the linkname will be a difficult task, that will take time and coordinate/check with relevant groups maintaining individual databases. Your patience will be greatly apprecired. [sic]
It took me a bit to decipher their suggestion on how to manually find all links, so I will share what I've learned. There is (currently) no codified or formal means to obtain all possible link names and I infer that many links exist simply because they are utilized in the internal workings of their website. I could be wrong about that, but suffice it to say that there are many undocumented links and they change constantly.
You can get a list of filter items using each individual database's advanced search web interface, "most of which should be the linkname from that source database to other target database". (So this should result in all possible links among a series of false positives.)
Here's how you do that. Let's take the gene database as an example:
- Go to the advanced search web page for that database, e.g. https://www.ncbi.nlm.nih.gov/gene/advanced
- In the "Builder" section, select "Filter"
- Click "Show Index List" to the right of the search term field next to the select list where you selected "Filter" (you will see a multi-select list appear below the search field)
- Click "Next 200" until you find a selection in that new select list matching the database name followed by "all" and a number in parentheses, e.g.
gene all (29994947)
and click to select that item 
- Click "Refresh index" at the lower right corner next to the multi-select list

The multi-select list will be repopulated and most of the items will be linknames (though you have to replace spaces with underscores in order for those linknames to work with the elink utility).
Doing this for the gene database and then scrolling through just links to nuccore (and its alias "nucleotide" - ignoring est and gss), you will find:
- gene nuccore
- gene nuccore clust
- gene nuccore mgc
- gene nuccore pos
- gene nuccore refseqgene
- gene nuccore refseqrna
- gene nucleotide
- gene nucleotide clust
- gene nucleotide mgc
- gene nucleotide mgc url
- gene nucleotide pos
If you look only at the linknames in the documentation or via einfo (by supplying the gene
database and looking at similar links to nuccore), you only get these links:
- gene_nuccore
- gene_nuccore_mgc
- gene_nuccore_refseqgene
- gene_nuccore_refseqrna
- gene_nucleotide_mgc_url
So I believe that given this information and the ever-changing nature of these links, I believe I will allow the user the option to enter a linkname manually, if the set in the select list I generate via einfo does not contain the link they need.