This article explains how I used the 'Backup to Gmail' application to backup all my SMS and MMS messages.
There are several applications that offer backup facilities, some backing up SMS or MMS some doing both. The thing I liked about 'Backup to Gmail' was that it can backup both message formats, and it can run as a scheduled backup and it allows you to restore messages as well.
The application can be downloaded from the marketplace ( https://market.android.com/details?id=net.cpedia.backup2gmail&rdid=net.cpedia.backup2gmail ) or on your device. It is not free, but for £1.20 I can hardly complain.
I downloaded it and logged in through Gmail and fired off a backup sync. Even on wifi it took a good hour to backup over 5000 SMS messages. You can specify different labels for the imported messages in Gmail, or you can leave it with the default labels of 'SMS' and 'MMS'. Imported messages appear just like emails in a conversation flow style.
After the import it must have taken ten to fifteen minutes to delete all the SMS messages from the phone, but it is a lot quicker now.