A few general suggestions (I haven't read your code thoroughly, sorry):
Pack your things (e.g. If the Link is broken, it is testing it if there's only a problem with the subfolder and generating a new url. Testing the head of this link) together in subroutines, your code will be clearer, more scalable.

Open and write to files once, don't open them every time. (time, performance)

About the question: If you find a broken link, you could save the line numbers in an array, and after you checked each line, you can delete the lines.
One solution that comes into my head is with Tie::File
Example of deleting the last line from a file, stolen from the Cookbook (hellyea, I am lazy):

use Tie::File;

tie @lines, Tie::File, $file        or die "can't update $file: $!";
delete $lines[-1];
[download]