Could a trained Megalodon shark or pair of them working in tandem be enough to sink the passenger ships and warships of the Victorian era?
A megalodon was roughly the size of a sperm whale. source
I asked Google "Could a whale sink a ship?" Answer: yes.
While it was the business of whalers to hunt and kill whales, sometimes a whale would fight back. Among the more famous of the several incidents of whales attacking whaling vessels are those of the ship Essex of Nantucket in 1820, the ship Pocahontas of Tisbury in 1850, the ship Ann Alexander of New Bedford in 1851, and the bark Kathleen of New Bedford in 1902.
All four stories have one element in common. The species encountered was a sperm whale and in each instant the whale rammed the vessel with its head after a prolonged fight with the whaleboats. The Essex under the command of George Pollard, Jr., with Owen Chase, first mate, sank two thousand miles off the west coast of South America in a region called the “Off Shore Grounds.” The whale attacked the ship “with vengeance in his aspect” according to Chase. The event became famous not only for the sinking itself, but for the terrible suffering of the crew members who were at sea for ninety days in three open whaleboats and gradually resorted to cannibalism with only eight of the original crew of twenty surviving.
What about a shark? Mythbusters modeled a great white (nonMegalodon) ramming a boat and confirmed that if their simulation was correct, a great white shark could punch a hole in the side of a wooden boat. from http://kwc.org/mythbusters/2005/07/special_jaws_special_1.html
Shark strength: Boat (Orca V) smashing
Myth: in Jaws, the shark pierces the side of the Orca and attacks the occupants within.
The setup was similar to the sharammer cage smashing. This time the sharammer pierced the size of the wooden boat and left a hole, though not quite Jaws-sized. The hole was above the waterline so the boat stayed afloat.
confirmed (a 3000 lb great white travelling at 25mph could pierce a boat)
So a great white has the speed and mass to punch a hole in a wooden boat, and sperm whales the size of megalodon actually did this to wooden boats.
I worry a real shark would not actually ram a wall of wood. Whales fight each other by ramming (among other maneuvers) and a sperm whale head makes a good ram. A shark rams a smaller thing in the context of an open mouth and a bite. The front end of a shark is not as good a ram as the front end of a whale.
In theory, a megalodon could sink a ship, probably by ramming.
Would a megalodon attack a ship by ramming? No, it would not. If we make the reasonable assumption that the megalodon is similar to the great white in physiology, we find that the great white hunts it's prey partially by detecting the electrical impulses of the nervous system. The great white does this with a number of sensors, located around the nose. This leads to two problems: Such sensors should reveal that a ship is not a living creature, and therefore not something that the megalodon would benefit from attacking. As well, it is unlikely that such a hunter would want to damage those electrical sensors in their nose by ramming, or to suffer any injury while attacking.
In the wild, injury is as good as death. In an injured state, the predator would be unable to hunt normally, and will probably starve before it can recover. You can see this with fish in the wild - smaller fish when faced with a larger predator will bristle up and send a message: I'm healthy, and I'm ready to fight. The predator fish usually backs off, not willing to risk injury, and goes searching for prey that is unlikely to fight back, like a sick or injured fish.
If you want something more realistic (and horrible) to send after a Victorian ship, try a giant squid. 25 foot long body, with 75 foot long tentacles. Have it pluck people off of the deck of the ship for a tasty snack.
Ok, my math may not be perfect here, but according to Wikipedia (and this paper) the bite force of a Megalodon could have been 108,514 N and 182,201 N.
Compared to the ramming example given in Will's answer, which puts the sharks ramming force at approx 15,200 N, a bite could be ten times more powerful then ramming. Meaning it should be more than capable of tearing a chunk out of a wooden ship.
When you add that to the fact a large Megalodon's jaws could be over 2m across then I would say two of them could do a considerable amount of damage to the wooden hull of a ship if trained correctly.
The main problem I can see is the relative flatness of the hull of a ship, which is not something the Megalodon could get it's teeth around. But if they could attack vertically and bite the keel they might be able to make a big enough hole to start causing a ship problems.
It's tricky, but it might just work. (albeit highly impractical)
The most pressing issue in this is "why" as in; why would a megalodon attack something that's bigger than itself. Sharks nowadays are simple creatures. They see prey and if they happen to be hungry and the prey they see isn't too large, they chomp it. Most shark attacks on surfers are actually the result of sharks mistaking an unlucky surfer for a meal and take a nibble.
The megalodonshark however is a lot bigger than a shark but it's brain isn't that much bigger. If you can somehow associate attacking Victorian ships with reward (food), they will definitely go for it, but you'll have to condition them to do so, which probably entails using life sized props in order to train your weaponized megalodonsharkfish.
As AlexP mentioned, you'll have to make sure your megalodonsharkfishthingy doesn't get injured upon attacking a ship. Once again this requires conditioning. So theoretically you could use this Megalodonsharkfishthingybeast as a weapon but it's highly impractical, time consuming and most likely not worth the effort when compared to a good ol' cannon with a chain-shot to ruin the mast and then just blast whomever you want to sink to kingdom come.
I think your megalodon shark attack would fare better if they leaped out of the water and landed on the enemy ship. They could easily capsize a smaller vessel in this manner, or shear off masts, rigging, and of course any unfortunate sailors on the deck of larger ships. A megalodon could be 50-60 feet long, almost twice the beam of many sailing ships, even a first rate like the HMS Victory was only 49' wide. Assuming a regular Great White can leap 3-5' out of the water and this scales proportionately to a megalodon, it could get 9-15 feet out. The Victory had around 30' of freeboard (hull above waterline) so a megalodon should be able to leap up enough to get most of it's body onto the top deck and be large enough to flop off after doing some damage.
In addition they could go after rudders. I'm not sure a shark has the anatomical features to allow it to effectively ram a military grade wooden hull or even bite it, but the rudder is much weaker. Even an early screw would be vulnerable. Disable the underwater control and propulsion surfaces, and disable the masts, and anything in the early to mid 19th century would be left drifting and vulnerable. But once steel hulls/masts became commonplace and larger screw propulsion drives were installed, shark attacks wouldn't be very effective (at least without critically/fatally injuring the shark in the process). At this point you are back to trying to attach limpet mines to seals and dolphins so they can make runs against the hulls/screws of enemy ships.
Sharks are extremely stupid. I don't think you can TRAIN them. But you can develop a reflex in them - for example, attack everything that has some flag.
Anyway, that process will take so much time and special tools, that it is not a problem to create one more tool - to give to a megalodon some sheath that will be fastened on its nose and will be hard and sharp. Then it will be able to cut a hole in any not armored ship.
Without such weapon even megalodon can do nothing to greater iron ships even of the 50-60-ties of 19Cent, let alone the 90-ties.
If you want to damage an ironclad, use megalodons with a weapon with a bomb on the end. Such living torpedoes would be effective even now.
Don't forget, that there is always some sort of dialogue in development of weapons and defenses. Better weapon - better defenses and so on. So you can reveal several secret weapons to the reader.
Put a large metal spike on their heads, attached to a skull cap that distributes the force along the cap, instead of into the shark's skull, and you've got the Nautilus.