The trick that fixed this for me was numbering the rows and columns on my graph paper along the edges, then treating every pad as a coordinate. So instead of trying to eyeball a spaghetti mess of lines, I write the route down as something like B4 to F9 via D6. Once I did that, losing track past a dozen connections basicly stopped happening. Crossings are also fine on paper, which they are not on a board once the iron is hot. Second thing: use a different colored pen per signal. Red for positive, black for ground, then whatever colors you have for the rest. It sounds like overkill until the day you can look at a page and instantly see that two blue lines are fighting for the same channel.
Third, and this is the big one: stop treating crossings as failures. On perfboard you have escape hatches you don't get with etched boards. You can hop a trace over a hole, run a wire on the underside, or just accept a jumper. The real battle is placement, not routing. Put the part with the most pins near the middle, power and connectors along the edges, and shuffle things around on paper until the crossing count drops. Ten minutes of shuffling saves an hour of braid work. My favorite physical trick is to seat everthing loose in the actual board, no solder, then lay bare jumper wire on top until the routing looks clean. Snap a photo from above, lift it all out, and now you have a build plan that you allready know fits. That photo is what I solder from.
And since this thread is about it, that PerfboardMaker tool someone linked does the route planning automatically, so if the pen and paper route still fights you, give it a shot. Free and all, nothing to lose. But honestly the numbered grid plus loose-fit-and-photograph method got me through years of boards before any software existed.