I have at least 2 things to tell you about.
My comments start with ##

sub add_entry {
    $log->print("Entering add_entry.", 3);
    my ($md5, $method, $key, $exists, $children) = @_;
    my ($parent, $parentmd5, $parentchildren);

    unless ( $children ) { $children = ''; }
## useless use of join
## "$key $exists $children" better used here
    $urldb->db_put($md5, (join(' ', $key, $exists, $children)));

    # It's an old entry--it already has parents.  Can leave.
## useless use of a regular expression
## if( index($children,':') != -1) { # better used here
    if ( $children =~ ':' ) {
        return;
    }

    $parent = find_parent($key);

    # No more parents, or can't parent ourselves...
    if ( $parent eq "http:/" or $parent eq $key ) {
        return;
    }

    $parentmd5 = uc(md5_hex($method, $parent));

    if ( $urldb->db_get($parentmd5, $object)==0 ) {
## inefficient use of split here
## see perlfunc split for more details (try the 3 arg)
## split /PATTERN/,EXPR,LIMIT
## so 
## $parentchildren = (split(' ',$object,3))[2];
        $parentchildren = (split (' ', $object))[2];
    }
    else {
        $parentchildren = '';
    }

    unless ( $md5 ) { $md5 = ''; $log->print("What, I say, what?!", 3)
+; }
    # Is this child already listed?
## style point, do you know what $foo =~ $bar is?
## are you going to remember?
## is $md5 a regex parrern?
## always be explicit (add //)
## useless use of a regex here as well
### unless(index($parentchildren,$md5) != -1) { # is better
    unless ( $parentchildren =~ $md5 ) {
        if ( $parentchildren ) {
            $log->print("Inserting parent: $parent with children: $par
+entchildren:$md5", 3);
            add_entry($parentmd5, $method, $parent, 0, "$parentchildre
+n:$md5");
        }
        else {
            $log->print("Inserting parent: $parent with child: $md5", 
+3);
            add_entry($parentmd5, $method, $parent, 0, $md5);
        }
    }
    return;
}
[download]

Now i've seen you test/manipulate $parentchildren a few times using m// or split ... you might think of turning $parentchildren into somekind of hash or something, cause memory is easier to spare than extra function calls, right? (i think so)

 

______crazyinsomniac_____________________________ Of all the things I've lost, I miss my mind the most. perl -e "$q=$_;map({chr unpack qq;H*;,$_}split(q;;,q*H*));print;$q/$q;"