The was a bug with early iOS 6 where it would store all message attachments, even if the message chat was deleted. It was fixed in 6.1 I believe but I think it returned, since my iCloud backups were growing pretty rapidly (iPhone 5 on 6.1.4 and an iPad Mini on 6.1.3).
There is software that you can use to get into your phones system files and delete attachments. If that isn't an option for you, a clean restore will fix it but the data backups will continue to grow again.
This is why I moved my iPhone and iPad backups back to iTunes, they were both taking up a 1GB of space and I only have the free 5GB plan.