If I reassert the package name at the beginning of a part file, it loses all of the other common preparatory code like use base or other modules.

use base, setting @ISA, @EXPORT*, @VERSION, etc., should only need doing once. It should be fine to just put package at the top of your sub-modules. If you are concerned that they might be used without the top Mod.pm, put a use Mod (); at the top for each sub-module.

Any ideas on how I can avoid 4000 lines of many module subs in one source file?

Why do you need to arbitrarily divide your module up? (If you had > 65535 lines and were using perls older than 5.8.1, I could understand.)