How about something like this? It produces the correct output for me, although you'll probably want the hash keys sorted some way. This may be a little sloppy for some folks, because it uses lots of auto-vivification to create the deep @tables structure. I don't mind, though.

use HTML::Template;

my $template = qq{
<TMPL_LOOP NAME=TABLE>
  <table border=1>
    <tr><th>key</th>
      <TMPL_LOOP NAME=KEYCELL>
        <td><TMPL_VAR NAME=KEY></td>
      </TMPL_LOOP>
    </tr><tr><th>value</th>
      <TMPL_LOOP NAME=VALCELL>
        <td><TMPL_VAR NAME=VAL></td>
      </TMPL_LOOP>
    </tr>
  </table>
</TMPL_LOOP>
};

my %somehash = map(("key$_" => "val$_"), 1..15);
my $maxwidth = 6;
my @tables = ();

my $num_items = 0;
for (keys %somehash) {
    my $table_num = int($num_items++ / $maxwidth);

    push @{$tables[$table_num]{keycell}}, { key => $_ };
    push @{$tables[$table_num]{valcell}}, { val => $somehash{$_} };

}

my $template = HTML::Template->new( scalarref => \$template );
$template->param( TABLE=>\@tables );
print $template->output;
[download]

-------------
This produces the output (keys are unsorted, as you can see):

key	key7	key8	key9	key10	key11	key12
value	val7	val8	val9	val10	val11	val12

key	key13	key14	key1	key15	key2	key3
value	val13	val14	val1	val15	val2	val3

key	key4	key5	key6
value	val4	val5	val6

I'd be interested to see if any masterful monks can reduce the for loop to a one-liner map() statement (or a two-liner if the keycell and valcell loops must be separated). Hope this helps, and good luck. (BTW, I modified your HTML template a little bit -- added indentation, border=1, and s/key/value/ in 7th line)

Update: to fit the specifications of your original question, you should change $maxwidth to 5, as you wanted a maximum of 6 cells including the <th> tags.