The solution states that the final step of the merge sort can perform this in O(n) time, but I am pretty sure this is incorrect.

The answer should be O(nlogk) where k is the # of departmental directory servers.

Am I reading this wrong?

You are correct. If you're clever about how you find the next element to merge (use a heap consisting of the next element from each of the lists you're merging), then it's O(n log k) as you state. If you're less clever and scan the next element of each list to find the next element to merge, then it's O(n k).

John