Is it possible to put one million tally marks on a piece of paper?

It depends on the size of the paper and the size of the tally marks. A standard 8 1/2 x 11 sheet wouldn't hold them if you used a pencil to mark them. But paper comes in rolls thousands of feet long, and you could pencil them all in on one of those. Additionally, with the contemporary automated printing techniques, a laser could be programmed to "burn" a million marks on a sheet of paper small enough that you could fold it up and carry it in a file folder with no difficulty.