Can you have a separate tile map for each island and just store where that tile map should be located?
Then you could render the ocean by finding the top left most visible tile by doing math.floor(visibleArea.left / tilewidth) and math.floor(visibleArea.top/ tilewidth) and drawing the water texture for every tile for as many tiles as fit vertically + 1 and horizontally + 1, as long as the Y value was under the water level.
Then you just need to render any visible islands.
So you memory foot print should be your textures and as many tile maps as you have islands. Which should be a lot smaller then one huge tile map of the whole world.
Edit: Wow totally missed the "Any other suggestions or perhaps how I could implement the above whilst still being able to use a* pathfinding?" sorry for the useless answer hopefully the below should help.
There are two ways to represent graphs. Adjacency graphs and edge vertex graphs. I prefer adjacency graphs for tile maps because you don't actually need to maintain an adjacency list just grab any of the the 9 surrounding tiles straight out of an array or generate them.
Point being for A* on a tile map you don't actually need a data structure containing the adjacent vertices since you can easily calculate it (assuming the graph would have a vertex for every passable grid tile would be adjacent to all possible vertices that are touching it).
You simply have to generate the adjacency list for every vert you pull a off the open list excluding any nodes on the black list or that are impassible. You can assume that all nodes are passable unless the vert is within an area that contains an island, in which case you will use the data from the tilemap to exclude any impassable tiles/verts.
Only real downside of this is that the graph is very dense. However, I doubt this would be an issue because from how I understand you game to be very little wasted effort on branches being explored that will dead end.
More simply you can just make a bee line for any targeted tile when in the water and then use A* to navigate any islands you come across.
There's only two cases I can see here
Case 1: You want to get to a tile on current island
Use A* to get from the first tile in the tile map you hit to the target tile.
Case 2: You want to get to a different island
Use A* to get from the current tile to the tile on the tile map that is closest in real space to the tile you want to get to.