Yes, you can create a FreeMarker template or JavaScript script that can perform this task by using an XPath //* style query that traverses all child descendants of a node.
Take a look at the example templates/scripts provided in the Data Dictionary.
And these are the docs pages (which also have many examples):
Looks like a time-consuming operation… since the number of document has to be shown on every request, it will be a better idea to create a node to hold the totals…
Yes it would be, it's a deep count operation after all.
Updating that value to keep it in sync might be tricky. A rule that runs at say 3:00am in the morning to perform the count and save the value might be worth doing if you can deal with it not being up-to-date.