|Think about Loose Coupling|
There are some benefits to using next or redo or a while or for loop instead of goto. One of those is, the perl compiler has more information about the structure of your code and its control flow, when you use something other than goto. I'm not going to make any uninformed assertions about the effects this has on optimization. Instead I'll bring up some more practical concerns.
If your target label in a goto is undefined, perl won't complain until it tries to actually execute the goto, even when using strict and warnings. If your goto is handling a "once in a thousand years" case, then you're likely not to notice this typo until it's too late. The same thing happens when a label gets deleted or changed inadvertantly. A case where the same label is used twice can cause other confusion, and I haven't seen use strict or warnings catch that case either.
If you are going to go through the trouble of making your code use strict, it's probably a good idea not to use code which subverts the strictness unnecessarily.
This is not to say "don't use goto," even though I tend not to like it. Just be aware of the potential consequences.
Finally, from perldoc -f goto:
The goto-LABEL form finds the statement labeled with LABEL and resumes execution there ... The author of Perl has never felt the need to use this form of goto (in Perl, that is--C is another matter).
Update:Abigail is right: labels on non-goto's have the same problem. I use labels on next when necessary, and much more frequently than I use goto. But I try not to use labels when they are not necessary, for the reasons I outlined above.