How to write a Serialize instance for this GADT?

What you're trying to do is impossible in general. Essentially, you're trying to get GHC to deduce Ixed a and Serialize (Index a) given only Serialize a. Granted, this may work for any use case you have in mind, but it doesn't generally work, which is why GHC is rejecting your instance.

I said "impossible in general" because if you specify the types you care about, then it's definitely possible. This means you'll have to list out all the types you have that can be serialized from Reorder, but that's really as good as you're going to get.

There are multiple ways to do this, but I think the simplest way is to use the constraints package to capture what you want in a Dict. You'd start by defining:

class MaybeSerializeIndexed a where
  canSerializeIndex :: Maybe (Dict (Ixed a, Serialize (Index a)))
  default canSerializeIndex :: (Ixed a, Serialize (Index a)) -> Maybe (Dict (Ixed a, Serialize (Index a)))
  canSerializeIndex = Just Dict

The default signature (which requires the DefaultSignatures pragma) is key to making your life simple as it means that you can list out the types you care about with easy one liners, as in:

instance Serialize a => MaybeSerializeIndexed [a]
instance Serialize k => MaybeSerializeIndexed (Map k a)

Beyond that, you can make an overlapping instance to deal with the types that don't work with Reorder:

instance {-# OVERLAPPABLE #-} MaybeSerializeIndexed a where
  canSerializeIndex = Nothing

With this machinery in place, you can write your instance:

instance (MaybeSerializeIndexed a, Serialize a) => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = do
    i <- getWord8
    case (i, canSerializeIndex @a) of
      (1, _)         -> Update <$> get
      (2, Just Dict) -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

Note that adding the MaybeSerializeIndexed a constraint to your instance is really not a big deal because there is an instance for every type. This also means that if you add a new type to your system without adding an MaybeSerializeIndexed instance for it, then you won't get a type error when you try to deserialize it—you'll only get a runtime error. For example, if you add a new type Foo where you know Ixed Foo and Serialize (Index Foo) but you don't add instance MaybeSerializeIndexed Foo, then you won't get a type error if you write a program that tries to get a Foo value, but you will get a runtime error when you run it.

As per @AntC's comment, it might be worth rethinking why you need Op as a GADT. However, here's one approach that seems to work...

It's kind of fundamental to Haskell that you can demand an instance Ixed a but not act conditionally depending on whether or not an instance Ixed a exists. So, one way or another, you're going to have to explicitly enumerate all the types a you want to use in this serialization and manually indicate which ones will and will not be treated as Ixed.

Once you've resigned yourself to that, there's a glaringly obvious solution. If you want to support Op a for a ~ Int (not Ixed) and a ~ [Int] (with Ixed), you can define two instances:

instance Serialize (Op Int) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

instance Serialize (Op [Int]) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      2 -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

and the main problem is solved. The remaining problem is how to make this boilerplate palatable.

Here's one way. We can define a type class to provide a getOp :: Op a operation, equipped with two instances, one for Ixed and one for non-Ixed types. The type class is parametrized in both a data kind Bool for the presence of Ixed and the underlying type, like so:

class OpVal' (hasixed :: Bool) a where
  getOp :: Get (Op a)

and the two instances are selected by the hasixed type, which specifies the capabilities of a:

instance (Serialize a) => OpVal' False a where
  getOp = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"
instance (Ixed a, Serialize (Index a), Serialize a) => OpVal' True a where
  getOp = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      2 -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

To select the proper instance for a type, we define a type family:

type family HasIxed a :: Bool

which specifies whether or not a type a has Ixed a. Then, we can use another type family to select the correct OpVal' instance based on HasIxed:

type family OpVal a where
  OpVal a = OpVal' (HasIxed a) a

Finally, we can define our Serialize (Op a) instance:

instance OpVal a => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = getOp @(HasIxed a)

With this in place, you can add types a to the open HasIxed type family:

type instance HasIxed Int = False
type instance HasIxed [Int] = True

and it all just kind of works:

instance OpVal a => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = getOp @(HasIxed a)

data BigThing a b = BigThing (Op a) (Op b) deriving (Generic)
instance (OpVal a, OpVal b) => Serialize (BigThing a b)

main = do
  let s = runPut $ put (BigThing (Update (5 :: Int)) (Reorder @[Int] [1,2,3]))
      Right (BigThing (Update x) (Reorder xs)) = runGet (get :: Get (BigThing Int [Int])) s
  print (x, xs)

The full example:

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

import GHC.Generics (Generic)
import Control.Lens (Index, Ixed)
import Data.Serialize

data Op a where
  Update :: Serialize a => a -> Op a
  Reorder :: (Ixed a, Serialize (Index a)) => [Index a] -> Op a

class OpVal' (hasixed :: Bool) a where
  getOp :: Get (Op a)
instance (Serialize a) => OpVal' False a where
  getOp = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"
instance (Ixed a, Serialize (Index a), Serialize a) => OpVal' True a where
  getOp = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      2 -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

type family HasIxed a :: Bool
type instance HasIxed Int = False
type instance HasIxed [Int] = True

type family OpVal a where
  OpVal a = OpVal' (HasIxed a) a

instance OpVal a => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = getOp @(HasIxed a)

data BigThing a b = BigThing (Op a) (Op b) deriving (Generic)
instance (OpVal a, OpVal b) => Serialize (BigThing a b)

main = do
  let s = runPut $ put (BigThing (Update (5 :: Int)) (Reorder @[Int] [1,2,3]))
      Right (BigThing (Update x) (Reorder xs)) = runGet (get :: Get (BigThing Int [Int])) s
  print (x, xs)