GOT IT! I was kind of lucky with that last bat coming up right next to the shrine, but I nevertheless made an interesting discovery that's used in this WIP: When trying to hit the bats in the East lair as soon as they come out, I can be somewhat closer to the top and still get them immediately. To be precise, I was using the Y position of 140 before, but it turns out that I can be as high as 128 and still hit the bat as soon as it comes out. This means that I didn't have to travel as much vertically between the West and East lairs.
WIP
EDIT: whoops, I didn't notice that managing to get 16 souls causes a house to be built on the special spot that causes a fire later. Considering that when building a road, going up then down past the shrine then up again prevented building a house in that special spot, perhaps taking the normal route of down then up might prevent it? It's worth a try, I guess.
EDIT #2: well, that didn't work out, so I went back to my previous WIP and delayed hitting the bat that would've earned me the 16th soul just long enough so that it didn't so before the first construction phase. Thanks to that (and perhaps also to more optimized killing of bats), I was able to barely get 6 houses in the second construction phase instead of 5, so I'm satisfied.
EDIT #3: except that that causes fires too. AAAAAARRRGGHHH!