In the beginning, there was a joke. A joke that said that Perl and Python would merge in a new language called Parrot.
And then come the idea of Perl6, and the name Parrot was given to a new virtual machine on which Perl6 will run.
You have that slightly out of order. The announcement of Perl 6 was in July 2000. Simon Cozens' Parrot joke was April 1st 2001. Here's Simon's article about the joke.
"The first rule of Perl club is you do not talk about
-- Chip Salzenberg