[Pamar]

According to this article: https://www.extremetech.com/extreme/134427-a-paper-based-bac... you can cram around 3MB of data (in a reasonably robust way) on the side of a sheet of paper - it is unclear if they mean A4 or Legal, though.

[michaelflux]

In the article they mention that they were using A4 sheets.