Tile Game slow. Lots of sprites. Texture atlas?

I had worked up some code for another question and realized that what I had was about 80% of the way towards what you were looking for. So I spent a bit of time and reworked the code. It produces a grid of a specified size. 600 x 600 is no problem and runs at 60+ fps in the editor. There are not a whole lot of lines of code, but the code is intricate. If you are going to try and use it, I encourage you to spend the time to understand every line...and there's no guarantee that I got everything right. I included a SetQuadUV method that will set a cell specified by row and column to a specified sprite sheet cell. I think from your description you will need cell-level hit testing. You could expand this code so that each mesh could report triangle hits, but I think you are better off putting a quad over the top of this mesh and doing the hit testing mathematically.

Here is the sprite sheet I used to test the code:

And here is the code:

 using UnityEngine;
 using System.Collections;
 
 public class TileGrid : MonoBehaviour {
     public Material material;
     public float cellWidth = 1.0f;  
     public float cellHeight = 1.0f;
     public int rows = 10;
     public int cols = 10;
     public int spriteRows = 2;      
     public int spriteCols = 2;
 
     private const int maxQuadsPerMesh = 16380;
     private int quadsPerMesh;
     private GameObject[] goMeshes;
     private Mesh[] meshes;
     private float spriteCellWidth;
     private float spriteCellHeight;
     private int spriteCellCount;
     private int rowsPerMesh;
 
     // Sets specified row/col to the specified sprite sheet cell 
     public void SetQuadUV(int row, int col, int cell) {
         int imesh = row / rowsPerMesh;
         int r = row % rowsPerMesh;
         int baseIndex = (r * cols + col) * 4;
         Vector2[] uvs = meshes[imesh].uv;
         SetMeshQuadUV(uvs, baseIndex, cell);
         meshes[imesh].uv = uvs;
     }
 
     void Awake() {
         spriteCellWidth =  1.0f / spriteCols;
         spriteCellHeight = 1.0f / spriteRows;
         spriteCellCount = spriteRows * spriteCols;
 
         CreateMeshes();
     }
 
     void CreateMeshes() {
         if (rows <= 0 || cols <= 0) return;
 
         quadsPerMesh = (maxQuadsPerMesh / cols) * cols;
 
         rowsPerMesh = quadsPerMesh / cols;
         int currRow = 0;
         
         int meshCount = (rows * cols) / quadsPerMesh + 1;
         int quadsLastMesh = (rows * cols) % quadsPerMesh;
 
         float height = rows * cellHeight;
         float width = cols * cellWidth;
         Vector3 offset = new Vector3(-width / 2.0f, height / 2.0f, 0.0f);
 
         goMeshes = new GameObject[meshCount];
         meshes = new Mesh[meshCount];
         
         for (int i = 0; i < meshCount; i++) {
             GameObject go = new GameObject();
             go.transform.parent = transform;
             MeshFilter mf = go.AddComponent<MeshFilter>();
             Mesh mesh = new Mesh();
             mf.mesh = mesh;
             Renderer rend = go.AddComponent<MeshRenderer>();
             rend.material = material;
             go.AddComponent<MeshCollider>();
 
             Vector3[] vertices;
             int l = 0;
             if (i != meshCount - 1) {
                 vertices = new Vector3[4 * quadsPerMesh];
                 l = quadsPerMesh / cols;
             }
             else {
                 vertices = new Vector3[4 * quadsLastMesh];
                 l = quadsLastMesh / cols;
             }
             
             for (int j = 0; j < cols; j++) {
                 for (int k = 0; k < l; k++) {
 
                     vertices[(k * cols + j) * 4]      = new Vector3(j * cellWidth, -(k + currRow)* cellHeight, 0.0f) + offset;
                     vertices[(k * cols + j) * 4 + 1]  = new Vector3(j * cellWidth, -(k + currRow + 1) * cellHeight, 0.0f) + offset;
                     vertices[(k * cols + j) * 4 + 2]  = new Vector3((j + 1) * cellWidth, -(k + currRow + 1) * cellHeight, 0.0f) + offset;
                     vertices[(k * cols + j) * 4 + 3]  = new Vector3((j + 1) * cellWidth, - (k + currRow) * cellHeight, 0.0f) + offset;
                 }
             }
 
             currRow += rowsPerMesh;
 
             mesh.vertices = vertices;
 
             int[] triangles = new int[mesh.vertices.Length / 2 * 3];
                 
             for (int j = 0; j < vertices.Length / 4; j++) {
 
                 triangles[j * 6 + 0] = j * 4 + 0;    //     0_ 3        0 ___ 3
                 triangles[j * 6 + 1] = j * 4 + 3;    //   | /         |    /|
                 triangles[j * 6 + 2] = j * 4 + 1;    //  1|/            1|/__|2
                 
                 triangles[j * 6 + 3] = j * 4 + 3;    //       3
                 triangles[j * 6 + 4] = j * 4 + 2;    //    /|
                 triangles[j * 6 + 5] = j * 4 + 1;    //  1/_|2
             }
 
             mesh.triangles = triangles;
 
             Vector2[] uvs = new Vector2[vertices.Length];
 
             // Sets random UVs for each cell
             for (int j = 0; j < vertices.Length / 4; j++) {
                 SetMeshQuadUV(uvs, j * 4, Random.Range (1, spriteCellCount));
             }
 
             mesh.uv = uvs;
             goMeshes[i] = go;
             meshes[i] = mesh;
         }
     }
 
     // Sets the uvs for one quad in a provided array of uvs
     void SetMeshQuadUV(Vector2[] uvs, int baseIndex, int cell) {
         cell = cell % spriteCellCount;
         float x = cell % spriteCols * spriteCellWidth;
         float y = cell / spriteRows * spriteCellHeight;
 
         uvs[baseIndex] = new Vector2(x + 0.01f, y + spriteCellWidth - 0.01f);
         uvs[baseIndex + 1] = new Vector2(x + 0.01f, y + 0.01f);
         uvs[baseIndex + 2] = new Vector2(x + spriteCellWidth - 0.01f, y + 0.01f);
         uvs[baseIndex + 3] = new Vector2(x + spriteCellWidth - 0.01f, y + spriteCellHeight - 0.01f);
     }
 
     // Press space bar to set random grid cell to sprite sheet cell 0
     void Update() {
         if (Input.GetKeyDown (KeyCode.Space)) {
             int i = Random.Range (0, rows);
             int j = Random.Range (0, cols);
 
             Debug.Log ("Row = " + i + "  Col = " + j);
             SetQuadUV(i, j, 0);
         }
     }
 }