Running numbers for a hypothetical worst case: 72 days (2**20 slots) of no progress on a shard, then one big crosslink. That’s a total of 2**35 bytes, or 2**38 bits; hence, each round would require 2**19 bits or 2**16 bytes (64 kB). And with the actual current proposed shard block size of 2**14 it would drop to ~45 kB.
That seems high but not fatal, it’s only several times higher than the theoretical max size of a slashable attestation. Also note that in this worst case, there’s only one attestation in a 72-day timespan that could be slashed. So the numbers do seem to imply that the two-step version (ie. descend by a square root at a time) could work fine. A nice property of the two-step version is that if the data is available, then once the attester responds to a challenge some third party could theoretically publish it immediately.