Some useful solutions have been provided, but no matter which approach you choose, you still need to be very confident about the quality of your input data for anything to work as intended. In particular, think what will happen if your input includes any two records like the following:

a1:b2:c3=foo
a1:b2=bar
[download]

This would create a logical contradiction: node "b2" shows up as both a leaf node and a parent node (it's supposed to hold both a string and a hash ref). Actually, whichever of these two records happens to come second in the input would obliterate data for the one that came earlier.

Unless you have perfect confidence in the input (that is, you have already tested it for well-formedness), you will want to include sanity checks in your hash-creation logic -- don't assign a scalar value to a hash element if it already exists as a reference, and don't use a hash element as a reference if it already contains a scalar. It may be easiest to add this sort of checking to the recursive solution proposed above -- to wit:

use strict;
use warnings;
use Data::Dumper;

my $tree = {};

while (<DATA>) {
    chomp;
    my ( $key, $val ) = split /=/, $_, 2;
    unless ( $key and $val ) {
        warn "Skipped bad input at line $. -- $_\n";
        next;
    }
    my $result = insert( $tree, $val, split( /:/, $key ));

    warn "$result -- skipped line $. -- $_\n" if ( $result ne "ok" );
}
print Dumper( $tree );

sub insert {
    my ( $tree, $val, @keys ) = @_;
    my $key = shift @keys;
    my $result;

    if ( @keys and exists( $tree->{$key} )) {
        if ( ref( $tree->{$key} ) eq 'HASH' ) {
            $result = insert( $tree->{$key}, $val, @keys );
        } else {
            $result = "Tried to overwrite string value as hash ref";
        }
    }
    elsif ( @keys ) {
        $tree->{$key} = {};
        $result = insert( $tree->{$key}, $val, @keys );
    }
    elsif ( exists( $tree->{$key} ) and ref( $tree->{$key} ) eq 'HASH'
+ ) {
        $result = "Tried to overwrite hash ref with string value";
    }
    else {  # Note: a scalar can still overwrite a prev. scalar
        $tree->{$key} = $val;
        $result = "ok";
    }
    return $result;
}

__DATA__
a1:b1:c1=first data record
a1:b2=second data record
a1:b2:c2=third data record
a1:b3:c2=fourth data record
a1:b3:c2=fifth data record
a1:b3=sixth record
a2:b1:c1:d1:seventh data record
a2:b1:c1:d1=eigth data record

__OUTPUT__
Tried to overwrite string value as hash ref -- skipped line 3 -- a1:b2
+:c2=third data record
Tried to overwrite hash ref with string value -- skipped line 6 -- a1:
+b3=sixth record
Skipped bad input at line 7 -- a2:b1:c1:d1:seventh data record
$VAR1 = {
          'a1' => {
                    'b3' => {
                              'c2' => 'fifth data record'
                            },
                    'b2' => 'second data record',
                    'b1' => {
                              'c1' => 'first data record'
                            }
                  },
          'a2' => {
                    'b1' => {
                              'c1' => {
                                        'd1' => 'eigth data record'
                                      }
                            }
                  }
        };
[download]