А если просто на листьях?
Достаточно большие листья некоторых пород деревьев и трав, имхо, могут сойти за "бумагу".(Пальмовые листья - в Индии, папирус в Египте... а в Валиноре что-нибудь подобное росло?)

Интересно было бы сравнить квенийские и синдарские слова для "листа бумаги" и "листа дерева" - но не факт, что они известны. (ухожу раскапывать словари)

Вдвойне интересно было бы задуматься, _зачем_ и _что_ писали, и отсюда двигаться к применяемым материалам. Для чего могли бы понадобиться именно бумажные записи? Что мы знаем о памяти эльфов?
Книги определенно _были_, Румил тому примером. А вот повседневные записи - уже не факт.

Если письменность - род искусства, а не быта в нашем его понимании, то материал мог соответствовать замыслу и быть в каждом отдельном случае - разным.
Но я, кажется, опять убрела в оффтопик.

P.S. Очень интересный с виду свиток прислал Арагорн Сэму - черный фон и серебряные буквы, если я правильно понимаю. Материал? Чернила? У меня пока никаких предположений.