We have to remember that we only ever have a squinting view at the past because >99% not made from stone of everything has rotted.
I have no doubt that we were writing on paper-like substances long, long before rock carving, but there's simply no remaining evidence of it the we know of.
Importantly, not all drawn symbols that convey meaning are writing. Musical notation is not writing for example. There's been an open debate in archaeology regarding the extent to which rock and cave art are actually conveying speech as opposed to some other form of communication and whether these practices are even directly related to early writing traditions.
what's fascinating is words, numbers, money and computation seem to have the same origin in those proto-cuneiform boxes.
The following reference may be of help:
How Writing Came About. By Denise Schmandt-Besserat. Austin: University of Texas Press, 1997. Pp. xii+193; figures, notes, index. $19.95.
This book is a summary of her earlier two volume study called 'Before Writing'.
Hope this helps.