In particular, how were large-scale operations like war campaigns organized, how were logistics tracked, and how did people ensure that complex chains of time-sensitive events were carried out correctly? What pen and paper (or other) methods existed?
The Gantt chart was originally a paper based project planning method. The Google article says
The first known tool of this type was developed in 1896 by Karol Adamiecki ... . The chart is named after Henry Gantt (1861–1919), who designed his chart around the years 1910–1915.
One of the first major applications of Gantt charts was by the United States during World War I ...
Gantt charts are sufficient (but a little out of fashion) for many projects, but as you begin to seek an optimal solution (in time, materials, people), more powerful tools become worthwhile.
Development and early use of PERT:
The Navy's Special Projects Office, charged with developing the Polaris-Submarine weapon system and the Fleet Ballistic Missile capability, has developed a statistical technique for measuring and forecasting progress in research and development programs. This program evaluation and review technique (code-named PERT) is applied as a decision-making tool designed to save time in achieving end-objectives, and is of particular interest to those engaged in research and development programs for which time is a critical factor.
Development and early use of Critical path method:
The precursors of what came to be known as Critical Path were developed and put into practice by DuPont between 1940 and 1943 and contributed to the success of the Manhattan Project.
Each of these tools were originally manual, but since they are strongly prescriptive techniques, they are readily implemented in software. For example, I recall that ICL had a PERT product in the mid-1970's.