I think something like this should probably be close to what you are looking for:

defmodule MyDiffingToolTest
  use ExUnit, async: true
  use ExUnitProperties
  import StreamData

  property "the Elixir tool works the same as the JS tool" do
    check all map_a <- map_of(term(), term()),
              map_b <- map_of(term(), term()) do
      assert JsLib.diff(map_a, map_b) == ElixirLib.diff(map_a, map_b)
    end
  end
end

And then inside JsLib you’d have some Elixir code that invokes the JS tool from within Elixir.
You might need to change term() into something like one_of([integer(), boolean(), string(), nil]) to restrict the types to only have things that can be JSON-encoded.

Writing a generator that can generate deeply nested JSON objects/arrays is also possible, but takes a little more work. (C.f. StreamData.tree/2)