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 [Math. Intelligencer 20 (1998)]. This way you can increase the perimeter just a bit, but it is done by repeating one fold (which is very simple but not "simple" in the sense below).
2. It is still not known if you can increase the perimeter by a sequence of natural folds; i.e., folds like this:
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.