Techniques and tools described herein help manage memory efficiently during video decoding, especially when multiple video clips are concurrently decoded. For example, with clip-adaptive memory usage, a decoder determines first memory usage settings expected to be sufficient for decoding of a video clip. The decoder also determines second memory usage settings known to be sufficient for decoding of the clip. During decoding, memory usage is initially set according to the first settings. Memory usage is adaptively increased during decoding, subject to theoretical limits in the second settings. With adaptive early release of side information, the decoder can release side information memory for a picture earlier than the decoder releases image plane memory for the picture. The decoder can also adapt memory usage for decoded transform coefficients depending on whether the coefficients are for intra-coded blocks or inter-coded blocks, and also exploit the relative sparseness of non-zero coefficient values.