Yes, there are a number of algorithms well-past the old mark & sweep. Throwing their names around isn't much use since most people are barely (if at all) familiar with m&s, let alone generational or threaded collectors of various sorts
Base structures are all allocated out of arenas, and most pointers to other base structures come from structures in the arena, so we're not walking through all of memory, instead usually being restricted to the arenas.
We don't currently have an incremental collector, though there's no reason we can't have one in the future. (The easy stuff first, after all... :)
The compilers are certainly within their rights to explicitly destroy variables. Given how introspective perl can be, though, that's not always wise. (With, say, caller %MY peeking and such)
We allocate memory out of pools. Out of memory for us is when we have no more pool space, not when the system has no more memory handy. (Memory usage can be restricted this way as well, but that's a side benefit)