What melachah is transgressed by folding a tallis? Is there some way to fold it which is permitted?
See Aruch HaShulchan OH 302:12 where he explains the common custom to fold our tallis on Shabbos because our folding does not fall under the category of fixing nor is it difficult to do.
ובזמנינו יש הרבה שמקפלין טליתותיהם בשבת, ויש לומר דסבירא ליה דבקיפול שלנו ליכא שום תיקון, וטעמא דטירחא לא סבירא ליה, כדעת רש"י והרמב"ם והטור והש"ע
And in our times there are many who fold their talleisos on Shabbat. You can say that they hold there is no improvement (tikkun) in our [manner of] folding. With regard to extra effort [on Shabbat] they hold it does no apply here, an opinion which is shared by Rashi and the Rambam and the Tur and the Shulchan Aruch.
There is an additional problem and it is the one of "mechin" (preparing) the tallit to be used after the Shabat, for Sunday morning or next Shabat if this is your tallit for Shabat. The solution for this is to fold the talit in a "non regular" form, e.g. different direction than you generally do. This means that after Shabat you will refold it. This gives an opportunity for another Mitzvah: Shlom Bait. Generally the husband got the tallit as the first present from his wife (then she was his bride). The first thing he does after Shabat, either before or just after Habdalah is to fold the tallit to show how much he cares for his wife's presents. This is a wonderful way to start a new week.
In contrast to the Aruch Hashulchan brought in this answer (and be sure to read Josh's link for some solid background information), The Mishna Berura on Shulchan Aruch OC 302:3 forbids folding the tallit after the completion of prayer unless the conditions listed below are met. It appears (See M"B SK 14 and others) that he holds it is forbidden because of "Nireh K'Mitaken Mana" - It appears as if one is one is fixing something (I'm not quite sure how to translate the halachic definition of metaken). However, perhaps from SK 19 it is possible to say that the Mishna Berura is also worried about preparing on the Shabbat for the weekday.
Here are the conditions that allow folding along the original folds on Shabbat:
The folding must be done for Shabbat itself (even though the mitzvah of tzitzit applies the whole day, if one does not intend to wear the tallit again that day it is forbidden. If the person wears the tallit by Mincha it is permitted to fold it after Mussaf M"B SK 13)
Only one person must do the folding (and he cannot fold it on a bench or the like - M"B SK 14)
They must be new, unwashed garments (new, unwashed garments are stiffer and therefore do not fold as nicely, and are therefore not considered as "Mitaken" M"B SK 15) - [I don't know how long a tallit is considered new. I don't have a source right now, but somewhere in Chapter 302 this is discussed with regards to a hat, the same thing would probably apply]
They must be white (folding colored garments "fixes" them better - M"B SK 16) - [As I brought in this answer, a Tallit is considered white, even though it has black stripes. I don't know if the tallit would also be considered white when concerned about folding on Shabbat though].
This must be his only garment, i.e. he is folding it so it should be nice for later. (If he has other Shabbat garments the Rabbis did not permit him to fold this one. - M"B SK 17)
The Shulchan Aruch then points out, and agrees with, the Mordechai who says that it is permissible to fold it not according to its original folds without a problem. The Mishna Berurah says that the Acharonim agree that this is the Din, but points out that if one wants to be strict and not fold it at all, it is still better.
My understanding is that folding is considered tikkun kli which is a toldah of makkeh b'patish, because by folding on the folds you are sharpening the creases.
To me this would apply where you want the crease, like on a pair of smart pants. Personally I would prefer my tallis to have no creases at all - creasing it spoils it rather than improving it.