undef $/; # slurp mode
$^I = ""; # enable in-place editing

This sounds like a nice job for Tie::File.

#!/usr/bin/perl -w
use Tie::File;
use strict;

my $max = 512;
my $file = 'syslog';

tie my @lines, 'Tie::File', $file;

my $size = 0;
for my $line (reverse -@lines .. -1) {
    if (($size += length $lines[$line]) > $max) {
        splice @lines, 0, (@lines + $line + 1);
        last;
    }
}

untie @lines;
[download]

(Didn't use negative splice length, because Tie::Splice seems to be unable to handle it.)

U28geW91IGNhbiBhbGwgcm90MTMgY
W5kIHBhY2soKS4gQnV0IGRvIHlvdS
ByZWNvZ25pc2UgQmFzZTY0IHdoZW4
geW91IHNlZSBpdD8gIC0tIEp1ZXJk