Go with tags, they are more powerful. Folders will force you into a hierarchy (if you can even have sub-folders).
With tags you can create arbitrary categories. So a "status" tag can be assigned to an email that already has a "report" tag but also to the one that has a "meetings" tag. In other words it is like being able to put the same object in two different folders.
One drawback of tags is, that it is harder to visualize. Google does a good job with searching but I can't think how you can visualize it (as a graph/hypergraph actually might work).
The other drawback is that people are more used to folder because they dealt with file systems before ("I'll make a folder for dates, then inside we'll split them by topic" kind of thinking).