Bitcoin does not use a stupid block propagation algorithm, such as would be needed to create exponential overhead.  It may have overhead that is constant in node connectivity, whereby a node receives the same block from each of its neighbors.  However, if so, this is easily fixed by flooding the small block header to each neighbor once, but having neighbors request the block data from only one neighbor.  In this case, each node receives only one copy of each block.  (Well connected nodes with many fast connections, may send multiple copies to many less connected nodes, but poorly connected nodes will send few copies, with the number of "takeoffs" being equal to the number of "landings".)  There is the opportunity for fine tuning the request process, so that nodes request data from new blocks from those neighbors that are known to have a fast ability to send them.  There may be some small overhead related to the discovery process.  (These kinds of issues exist in other peer to peer networks such as bittorrent and have been solved.)