I stumbled on a collapsible bag from Muji in Tokyo recently.
Paraglider Foldable Boston Bag Black
Packs down pretty small and for the price I can't complain.
I also have one of Sea-To-Summit's ultra-packable tote bags. Packs down to about the size of shot glass but expands to the size of a grocery bag. Serves as an excellent travel companion for toting around dirty clothes, a picnic lunch, souvenirs on the flight home, clothes for a day at the beach, etc.
I think it's this one:
Ultra-SilŪ Sling Bag | Sea to Summit