the factory method and the constructor (which the factory would use) would both be methods of the same class

In theory, it'd be possible for this "constructor" to return an object of a different class. But I don't see why the constructor would need to be a member of the factory class?

Anyway, here's my interpretation of your description. Note how Object still has a formal new constructor, but it could be documented that users should not call it directly, but use Factory methods instead - it could even be named _new to make that even more clear.

use warnings;
use strict;

package Factory {
    sub new {
        my ($class,%args) = @_;
        my $self = {
                config => _read_config( $args{config_file} ),
            };
        return bless $self, $class;
    }
    sub _read_config {
        my $file = shift;
        my %config;
        # ...
        return \%config;
    }
    sub make_object_from_data {
        my ($self,$data) = @_;
        my %args;
        # complex code to build %args from $data using $self->{config}
        return Object->new(%args);
    }
}

package Object {
    sub new {
        my ($class,%args) = @_;
        my $self = \%args;
        return bless $self, $class;
    }
    # ...
}

my $factory = Factory->new( config_file => "file.xml" );
my $obj1 = $factory->make_object_from_data( { foo=>123 } );
my $obj2 = $factory->make_object_from_data( { bar=>456 } );
[download]

However, looking at this, here's how I might have structured this code. It has the advantage that "Object->new" isn't hardcoded, making subclassing of that class easier. To me, it feels more in line with the requirements as far as you've described them.

use warnings;
use strict;

package Config {
    sub new {
        my ($class,%args) = @_;
        my $self = {};
        # code to read $args{config_file} into $self
        return bless $self, $class;
    }
}

package Object {
    sub new {
        my ($class,%args) = @_;
        my $self = _parse_data_with_config($args{config},$args{data});
        return bless $self, $class;
    }
    sub _parse_data_with_config {
        my ($config, $data) = @_;
        my $self = {};
        # complex code to build $self from $data using $config
        return $self;
    }
    # ...
}

my $config = Config->new( config_file => "file.xml" );
my $obj1 = Object->new( config => $config, data => { foo=>123 } );
my $obj2 = Object->new( config => $config, data => { bar=>456 } );
[download]

Of course it'd be possible to add a method to Config like this:

    sub new_object {
        my ($self,$data) = @_;
        return Object->new( config=>$self, data=>$data );
    }

# ... call as:
my $obj3 = $config->new_object( { quz=>789 } );
[download]

... and you'd have something very similar to my first example.

As you can see, I've put the "complex code" into a sub in each case, and as you can tell, except for the variable names, these subs could be pretty much identical in both examples. This means that the surrounding code could be refactored more easily if you decide that a different API makes more sense. Unless you've got more complex requirements you haven't told us about, I'd suggest just starting with one API - once you actually start using your own API you will quickly notice whether it is good or a different API would be better. And if you've structured your code in a way that makes refactoring easier, you'll be less hesitant to do so.

since you even used the word "configure", why not make a class variable, and have the Configure sub set that variable (or just write it directly)? You would have to have a lot more protection/error-checking than in this example, but the proof-of-concept could be:

package MyClass;
use warnings;
use strict;

our %Config;

sub Configure {
    %Config = %{$_[0]};
}

sub new {
    my $class = shift;
    my $self = {%Config};
    my %args = @_;
    foreach (keys %args) {
        $self->{$_} = $args{$_};
    }
    return bless $self, $class;
}


package main;
use warnings;
use strict;
use Data::Dumper;

MyClass::Configure( {group => 1, defined => 'values'});
my $x = MyClass->new();
my $y = MyClass->new(extra => 'here');
MyClass::Configure( {group => 2, defined => 0});
my $z = MyClass->new(third => 3);

$/ = "\n";
print Dumper $_ for $x, $y, $z;
[download]