You search the same regions multiple times. If neighbour #1, 2 and 3 are all connected to the outside, you search the outside of the map three times when you already knew the right answer from neighbour 1's visited set.
Start at an adjacent tile of your own territory, then walk the neighbours in order until you come to another player's territory. Search there. Then walk until you find the next tile of your own territory, skipping any others (since you know they border the same set). Check if the next other-player tile after that is already in the visited set before starting a new search. This simple optimization should cut the search time down by half or better.
You're using LINQ expressions like player.myCells.Select(x => x.Index).Concat(visited). This is great for compact, expressive, readable code, but you pay a cost in performance.
Consider having a read-only array of tile offsets. Then this code could look something like:
for (int i = 0; i < 6; i++) {
int neighbourIndex = currentTile + NeighbourOffests[i];
if (playerOwner[neighbourIndex] != thisPlayer
&& !visited.Contains(neighbourIndex)) {
queue.Add(neighbourIndex);
visited.Add(neighbourIndex);
}
}
It's a little more verbose, but it's dead simple to execute.
You're re-creating your data structures every time you call this function. Since this is something your game needs to do frequently, create your data structures once, and re-use them.
C#'s System.Collections types get created with a small capacity at first, and gradually re-allocate to larger and larger sizes as you fill them up. If you're creating new ones all the time, you're paying that memory re-allocation cost on every tile placement. But if you re-use them, you pay the "warm-up" cost once, and then continue benefitting from it for free.
This is also why, if you have a good idea of how many items you'll need to store in the collection (and that number is big), it's a good idea to pass in that initial capacity to their constructor so they can pre-size themselves appropriately, rather than working up to it over several re-allocations as the collection grows.
You're using a HashSet for what could be a visited flag on each cell in an array. Yes, they're both \$O(1)\$, but looking up this information in a HashSet requires hashing the key and pseudo-random memory access, so it will be noticeably slower. HashSet structures are good for when the space of all possible set members is too big to reasonably allocate memory for all of them in an array, but here it's just your map size, so simpler options are available.
In particular, iterating the keys of a hashmap is slow, which is what Concat(visited) has to do.
You're using breadth-first search. This explores cells in order of their distance from the starting point, meaning if your new tile is in the middle of the map, you'll explore an expanding ring out to 50 tiles in all directions (about 7 850 tiles), instead of walking the 50 tiles to the nearest edge. This could be a good use case for depth-first search, or possibly even A* with a heuristic to seek toward the closest edge of the map.
A quick hacky version of that would be to use depth-first search with an array of neighbour offsets as suggested above, but select which neighbour offset array to use based on the position of your starting tile. You can have 6 different orderings of the neighbours, one trying each cardinal direction first. So choosing the down-prioritized neighbour set when your starting tile is close to the bottom of the map might get you similar behaviour to A*'s heuristic-seeking, but with lower code complexity.
