How to reproduce:
1. Create a new project
2. Import the prefab "prefab.unitypackage"
3. Drag the prefab to Hierarchy
4. Enter Play mode

Expected result: entering play mode takes around 1-2 seconds
Actual result: enter Play mode takes around 1-2 minutes, leaving the Play mode takes around 3-5 minutes

Reproducible with: 2019.1.0b10, 2019.1.14f1, 2019.2.0a10, 2019.2.21f1, 2019.3.12f1, 2020.1.0b8, 2020.2.0a9
Not reproducible with: 2018.4.0f1, 2018.4.22f1, 2019.1.0a1, 2019.1.0b7
Could not test with: 2017.4.40f1 (old prefab system)

Workaround information: The internal data structure of the Tilemap has changed for better runtime memory usage. Tilemaps which are loaded, for example in the scene, will be updated to use the new internal data structure. Unfortunately, the Tilemaps in prefabs will not be updated unless they are loaded (causing an update) and saved back as a prefab asset. This causes a slowdown for Tilemap prefab instances as the Tilemap instance in the scene differs from the Tilemap in the prefab, as shown in the Profiler, because the Tilemap instance has been updated while the prefab asset has not.

To resolve this, you will need to update the Tilemap prefab asset. You can do so with the following steps:

Select the Tilemap prefab asset in the Project Window
Double-click and open it in Prefab mode
Dirty the prefab instance to trigger the Save option (eg. changing and resetting the X position for the transform
Save the Tilemap prefab asset