You keep adding and modifying the same object for all the keys.
What you currently do can be viewed as this:

So to fix that, create a new Set at each iteration of the loop.
Map<Integer, List<String>> mapList = new TreeMap<>();
Map<Integer, Set<String>> mapSet = new TreeMap<>();
for (Map.Entry<Integer, List<String>> entry : entriesSortedByValues(mapList)) {
Set<String> set = new TreeSet<>();
set.addAll(entry.getValue());
mapSet.put(entry.getKey(), set);
}
Also you could use the constructor that takes a collection as parameter.
Map<Integer, List<String>> mapList = new TreeMap<>();
Map<Integer, Set<String>> mapSet = new TreeMap<>();
for (Map.Entry<Integer, List<String>> entry : entriesSortedByValues(mapList)) {
mapSet.put(entry.getKey(), new TreeSet<>(entry.getValue()));
}