O Millennium Falcon tem uma longa história, explicada no Wookiepedia e eu o encorajo a lê-lo aqui .
A parte importante dessa página é a seguinte citação:
The Second Chance [the Millennium Falcon before it was rechristened] was briefly rechristened the Gone to Pieces during this operation, but when he began flying the ship for the Alliance, he rechristened her the Millennium Falcon, after the bat-falcon
Apenas para notar, na citação acima, Wookiepedia explica que 'ele' é Zenn Bien que havia roubado, no entanto, esta fonte faz parecer que foi Quip Fargil quem o rebatizou de Millennium Falcon , mas também concorda que foi depois de um 'falcão de morcego'.
Agora, um "falcão-morcego" era:
a swift species of flying creatures. It inspired the name of the starship Millennium Falcon.
( Fonte )
Isso explica a parte do "falcão"; quanto à parte 'Millennium' do nome, suspeito (note que não tenho nenhuma evidência para isso, mas acho que é uma especulação razoável) que foi assim chamado porque 'Millennium' soava futurista; considere quando Star Wars foi lançado - não foi muito longe da virada do milênio, mas longe o suficiente para fazer parecer muito futurista. Apenas os meus pensamentos sobre esta parte, mas vou continuar a tentar encontrar qualquer prova a este respeito.