It has been years since I've stitched a map together but I used to have a program that did it for you.
You just had to open the program and scan the map in segments. This usually amounted to 9 scans for my maps. During the scanning you told the program what went where.
Then you clicked auto stitch and the program rotated the individual images to suit and gave you a flawless map.

It gave a much faster and better looking result than Photoshop ever did.

I stopped doing it when I started working at a place that had a scanner that could do a full map in one go.