You might use Time::HiRes in conjunction with the randomness offered by File::Temp. Since you can pass File::Temp a template to use for the filename, you could pass it something like $template = "yourfile-" . gettimeofday() . "XXXXX.xml"; so you'd still get what you want without interfering with filename sort order and it would also be a unique name.

If the file you're generating isn't necessarily a temp file, you could still use File::Temp to do nothing more than generate you a file name. (undef, $filename) = tempfile($template, OPEN => 0);