Is it because I don't have package defined at the top of the module? Therefore it's assuming the subroutine is part of Main?

Yes. All the () on use Foo () does is suppress calling Foo->import - when the module directly defines things in the main package, or exports things in its toplevel code, that's not affected.