Does Constants use package? If not, you should be using do, not use:

A.pm
----
# Order doesn't matter.
BEGIN { do 'Constants.pm' }
use B;
[download]

B.pm
----
BEGIN { do 'Constants.pm' }
[download]

use will only run the module once.

If Constants uses package, then Constants must export the constants:

A.pm
----
# Order doesn't matter.
use Constants;
use B;
[download]

B.pm
----
use Constants;
[download]