Now both methods get called before the constructor gets called
No, the order is:
- OnDeserializingMethod
 
- .ctor
 
- OnDeserializedMethod
 
And how can a (non-static) method be called before any constructor has been executed? 
Because it cheats and lies; it doesn't create the object with the constructor; no - really. It uses FormatterServices.GetUninitializedObject to allocate vanilla empty space. And then if there is a custom deserialization constructor it invokes the constructor over the top of that object. Nasty. Like this, basically:
var obj = FormatterServices.GetUninitializedObject(typeof(MyClass));
var ctor = obj.GetType().GetConstructor(
    BindingFlags.Instance | BindingFlags.Public| BindingFlags.NonPublic,
    null,
    new[] { typeof(SerializationInfo), typeof(StreamingContext) },
    null);
ctor.Invoke(obj, new object[2]);
IMO they probably should have made this a second method on the ISerializable interface, but for whatever reason: they didn't. A shame really: that would have made it more honest, and avoided people needing to remember to implement the custom constructor.
Example output:
.ctor: MyClass
> serializing
OnSerializingMethod: MyClass
GetObjectData: MyClass
OnSerializedMethod: MyClass
< serializing
> deserializing
OnDeserializingMethod: MyClass
.ctor: MyClass
OnDeserializedMethod: MyClass
< deserializing
Example code:
using System;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
[Serializable]
class MyClass : ISerializable
{
    public MyClass() { Trace(); }
    protected MyClass(SerializationInfo info, StreamingContext context) { Trace(); }
    public void GetObjectData(SerializationInfo info, StreamingContext context) { Trace(); }
    void Trace([CallerMemberName] string caller = null)
    {
        System.Console.WriteLine("{0}: {1}", caller, GetType().Name);
    }
    [OnDeserializing()]
    internal void OnDeserializingMethod(StreamingContext context) { Trace(); }
    [OnDeserialized()]
    internal void OnDeserializedMethod(StreamingContext context) { Trace(); }
    [OnSerializing()]
    internal void OnSerializingMethod(StreamingContext context) { Trace(); }
    [OnSerialized()]
    internal void OnSerializedMethod(StreamingContext context) { Trace(); }
    static void Main()
    {
        using (var ms = new MemoryStream())
        {
            var orig = new MyClass();
            var ser = new BinaryFormatter();
            System.Console.WriteLine("> serializing");
            ser.Serialize(ms, orig);
            System.Console.WriteLine("< serializing");
            ms.Position = 0;
            System.Console.WriteLine("> deserializing");
            ser.Deserialize(ms);
            System.Console.WriteLine("< deserializing");
        }
    }
}