Algorithm for determining minimal set of covering prefixes
Your algorithm will work. The information you will be looking for can be found in the prefix tree (trie) will hold the information you are looking for. 

Despite similarity in names, the set cover and this problem are not similar. The first is NP-Hard. This one is not. 

However (in relation to Point 3 of your algorithm), a tree node that is not a leaf may be the end of a word $w$ contained in other words (e.g. "be" contained in "bee" "behavior" etc .. ). You should take into consideration when counting. 

Point 4: Now we know each prefix and how many matches it has - I believe complexity is $n \log n$ .. why ? I dont think so. It is $O(n m)$. 

Point 6: I dont know though why you want to sort. You can find the max (which is $O(n)$). 

If you are going to present the tree in a relational database, then make sure you present it in a good way. For instance, try to make the whole tree in a single page, or close nodes in the tree in the same page. This is to minimize the I/O cost.  How to do that ? I honestly don't know. For me, I would just put it the prefix tree in a single binary file. Or a seriazable data structure.