In order to be able to see the red souls, you must first complete the Cantaloupe quest. This quest is available right after you complete gold mine and return back to Imasho town.

Requirement: Meet Kotaro before this side quest.

Go inside the item shop, then talk to a man standing near a group of people chatting. He'll give you Chalk in hope that you can trade it for Cantaloupe for him.

Then go back to the bar (you can use the side door in the item shop to quickly enter the bar) and do the following trades

1. Give Chalk to Ekei, well as expected, he is unhappy but still accepts anyway, and will give you Tale of the Heike.
2. Take the Tale of the Heike and give it to Magoichi. You'll always receive Emblem. Skip 2 steps below if you play on Oyu Route.
3. Take the Emblem, go upstairs and give it to Kotaro for Canteloupe.
4. Finally, take the Canteloupe back to the quest giver in the item shop.

After you came back from Gifu Castle and visit the Imasho town for the third time, go into the item shop and talk to the man who gave you the Cantaloupe quest previously to claim your reward:

Go to "Inventory -> Equip -> Armor" then equip the "Orange Necklace", you just got.

Hidden Red Souls #1: 

Gold Mine, in front of the gold mine entrance, near the guard's station.

Hidden Red Souls #2: 

Gold mine, inside the entrance, in front of the left path.

Hidden Red Souls #3: 

Gold Mine, second area before the split path, above the exit.

Hidden Red Souls #4: 

Gold Mine, northeast dead-end, go pass the boss room, after the hole.

Hidden Red Souls #5: 

Yagyu Village, in front of the Yagyu residence.

Hidden Red Souls #6: 

Yagyu Village, on top of the Lightning Dragon Shrine at the pond area, cave entrance.

Hidden Red Souls #7:

Yagyu Village, residence, inside the second room in the backyard.

Hidden Red Souls #8: 

Fog Valley, at the end of the skybridge.

Hidden Red Souls #9: 

Fog Valley, on top of the cliff near the Wind Dragon Shrine.

Hidden Red Souls #10: 

Fog Valley, mountain river, at the end of the river stream.

Hidden Red Souls #11: 

Fog Valley, inside the cave's entrance, right pond.

Hidden Red Souls #12: 

Fog Valley, room before Jujudormah boss just above the "Gerohone" hidden behind its tentacle.

Hidden Red Souls #13: 

Fog Valley, mid-way through the gas passage after defeated Jujudormah.

Hidden Red Souls #14: 

Onigashima 1F, entrance, east side of the beach.

Hidden Red Souls #15: 

Onigashima 1F, just above the Earth Dragon Shrine.

Hidden Red Souls #16: 

Onigashima 1F, east area, above the acid-pond room.

Hidden Red Souls #17: 

Onigashima 1F, east area, in the water tank room after the orange sealed.

Hidden Red Souls #18: 

Onigashima 1F, inside the light wall, at the end of the Bridge of Darkness.

Hidden Red Souls #19: 

Onigashima Underground, above the door to the factory room.

Hidden Red Souls #20: 

Onigashima Underground, in the west corner.

Hidden Red Souls #21: 

Gifu Castle East Area, northwest corner of the tower roof.

Hidden Red Souls #22: 

Gifu Castle East Area, inside the tower floating in midair.

Hidden Red Souls #23: 

Gifu Castle East Area, just outside the tower, in front of the door to the Green Phantom Realm.

Hidden Red Souls #24: 

Gifu Castle Keep Tower, just above the underground spiral stairs in the courtyard.

Hidden Red Souls #25: 

Gifu Castle Keep Tower, above the west door in the courtyard.

Hidden Red Souls #26:

Gifu Castle Keep Tower, second room after the Keep hall.

Hidden Red Souls #27: 

Gifu Castle Keep Tower, inside the green-seal door, behind the skeleton wall.

Hidden Red Souls #28: 

Gifu Castle Keep Tower, from #27, west area where you got the iron horse.

Hidden Red Souls #29: 

Gifu Castle Keep Tower, Keep Hall, 2F, to the east above the broken staircase.

Hidden Red Souls #30: 

Demon Cave, west path of the Demon Cave loop.

Hidden Red Souls #31: 

Demon Cave, at the end of the drawbridge.

Hidden Red Souls #32: 

Demon Cave, east path on the right side of the green seal.

Hidden Red Souls #33: 

Gifu Castle Keep Tower, lakeside, just above the door.

Hidden Red Souls #34: 

Gifu Castle East Area, at the boat house, dock, facing to the lakehouse to the see the red souls.

Hidden Red Souls #35: 

Gifu Castle East Area, lakehouse, just above the two petrified miners.

Hidden Red Souls #36: 

Onigashima Passages, On the right side of the entrance door.

Hidden Red Souls #37: 

Onigashima Passages, right above the hallway after the entrance door.

Hidden Red Souls #38: 

Onigashima Passages, just above the statue in the arena.

Hidden Red Souls #39: 

Airship, engine room, at the end of the hallway.

Hidden Red Souls #40: 

Gifu Castle Keep Tower, Keep's rooftop, right before the demon base.