In addition to the answers above, here are some remarks from [my paper in Russian][1]; part of it used in the [last lecture here][2].
(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][3]

**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][4]
I just learned that this problem also appears in [Pak's book][5], Problem 40.16b;
it is marked by [$*$] which means that the problem is open.


  [1]: http://front.math.ucdavis.edu/1004.0545
  [2]: http://arxiv.org/abs/1405.6606
  [3]: http://www.math.psu.edu/petrunin/papers/arnold/pics/yasch-hq.png
  [4]: http://www.math.psu.edu/petrunin/papers/arnold/pics/otgib-hq.png
  [5]: http://www.math.ucla.edu/~pak/book.htm