As it turns out the reason for this problem was one filename with several newlines. (No idea how that happened.)
find ~/x/y/ | shuf > ~/Desktop/z.txt
This command works pretty much as expected except some empty lines appear in the "z.txt" file. This is inconvenient because the next step is to pick the uppermost file and open it, an empty line would obviously be useless. I'm curious why this happens and if there is some "standard" solution to the problem (some option?), or, alternatively, some robust and simple solution (an extra command to delete empty lines?).