Test harness:
 proc testem {len} {
    for {set i 0} {$i < $len} {incr i} {
        lappend l1 a
        lappend l2 b
    }
    set res {}
    foreach p $cases {
        puts -nonewline stderr "$p..." ; flush stderr
        lappend res $p,$len [lindex [time {llength [$p $l1 $l2]} 100] 0]
    }
    return $res
 }

Candidates:

 proc SET         {l1 l2} { set l1 "$l1 $l2" }
 proc APPEND      {l1 l2} { append l1 " $l2" }
 proc CONCAT      {l1 l2} { set l1 [concat $l1 $l2] }
 proc EVAL/APPEND {l1 l2} { eval [list lappend l1] $l2 }
 proc FOREACH/LAPPEND {l1 l2} {foreach i $l2 {lappend l1 $i}; set l1}
----
 Tcl 8.4a4
 |-------------------------------------------| 
 | Method          | 10 | 100 | 1000 | 10000 | 
 |-----------------|----|-----|------|-------| 
 | SET             | 21 | 148 | 6777 | 69467 | 
 | APPEND          | 29 | 475 | 7993 | 81514 | 
 | CONCAT          |  9 |  15 |  312 |  5968 | 
 | EVAL/LAPPEND    | 15 |  23 |  393 |  6065 | 
 | FOREACH/LAPPEND | 18 | 369 | 4524 | 44235 | 
 |-------------------------------------------|