Now, at what point, do you do the Fisher-Yates thing in your code.. when you've got a larger array to deal with I guess - but how large?

I'd suggest always using it. Using List::Util makes it simple, and List::Util is core as of perl 5.8.0. If, for some reason, you can't use List::Util, the algorithm is pretty simple, and is listed there in perlfaq4 for you.

Tried looking to see if List::Util uses a Fisher-Yates but it seems to be a .so binary, a library.

There is a C implementation, compiled into the library you mentioned, and a backup Perl implementation. You can read the Perl implementation by opening the file printed with perl -MList::Util -wle 'print $INC{"List/Util.pm"}' in your favorite editor. The C implementation requires viewing the perl source, shuffle is in ext/List/Util/Util.xs. Both are implementations of the Fisher-Yates algorithm.

As for feeling bad about splice, you should never feel bad about using tools. Generally, you should write your code first so that it is readable, maintainable, and possibly portable, then start worrying about efficiency, preferably after you've done some profiling.