In addition to the answers above, here are some remarks from my paper in Russian; part of it used in the last lecture here. (Sorry for self-advertisement.)
1. An other solution. It is based on idea of Yashenko. This way you can incresae the perimeter just a bit, but it is done by repeating one fold (which is very simple but not "simple" in the sense below).
alt text http://www.math.psu.edu/petrunin/papers/arnold/pics/yasch-hq.png
2. It is still not known if you can increase the perimeter by a sequence of natural folds; i.e., folds like this: alt text http://www.math.psu.edu/petrunin/papers/arnold/pics/otgib-hq.png
I just learned that this problem also appears in Pak's book, Problem 40.16b; it is marked by [$*$] which means that the problem is open.