Innovations for category-prefixed data batching (“CPDB”) of entropy-coded data or other payload data for coded media data, as well as innovations for corresponding recovery of the entropy-coded data (or other payload data) formatted with CPDB. The CPDB can be used in conjunction with coding/decoding for video content, image content, audio content or another type of content. For example, after receiving coded media data in multiple categories from encoding units, a formatting tool formats payload data with CPDB, generating a batch prefix for a batch of the CPDB-formatted payload data. The batch prefix includes a category identifier and a data quantity indicator. The formatting tool outputs the CPDB-formatted payload data to a bitstream. At the decoder side, a formatting tool receives the CPDB-formatted payload data in a bitstream, recovers the payload data from the CPDB-formatted payload data, and outputs the payload data (e.g., to decoding units).