Nice project 
I am fond of algorithmic code, and really like to delve into these sort of projects.
I have a suggestion based on similar work I did for one of my projects: I maintain an open source client-side full text search engine (JavaScript, not Elixir), that uses a radix tree (similar enough to a trie) under the hood as the index data structure.
I like to keep the API of the data structure very generic, and compose use-case specific code on top of it. In this case, what you could do, is implement the trie to basically expose the same API as a Map (limited to string keys), plus a few functions to expose the prefix search features. You already implement the Access behavior, so you’re on a good track with it.
The prefix search function could then return another trie (the sub-trie at that prefix) instead of a list of words. If the trie implements the Enumerable protocol, it would be easy enough to turn it into a list of entries.
The advantage would be that your Trie could be used for any use-case where it is a good match. Essentially, any case in which one needs a map of strings to values with efficient prefix search.
In my project, where I essentially apply what I just wrote, the basic data structure code is documented here. It’s JS, but it illustrates my point above.
