Your problem is probably the mirroring. You’ve got a right side and a left side, and they’re both trying to bake their normals to the same UV space. Poor Blender doesn’t know what to do and just assigns the normals from one side to one triangles, and the normals from the other side to another triangle.
So what you want to do is bake the normals from only one side. Now, Blender only bakes normals from polygons of which the UVs are in the 0-1 space (that default square), so UVs placed outside get ignored completely. But the end result does tile. So just move one half of the UV to the 1-2 space.
That means you select the UVs of one half of your model, the part you want to be mirrored. Press G and offset them by the size of the image you have in the UV editor. So if you have a 512x512 image, just press G, 512. They should be ignored in the baking process now, but they’ll still share the outcome.
It should be noted that Blender, as far as I know, can’t actually display models with mirrored normal maps properly, so be sure to test the end result somewhere else.