If Psy-clops, who's not a big fan of Logan, has his way, the latter could be there for a while. Eventually Logan would be found, and Psy-clops gets a raise for keeping spending low.
Concrete corrodes when exposed to seawater. It also breaks down under a lot of pressure - anywhere from 2000 to 19000 psi, depending on the grade. The pressure at the bottom of the Mariana trench is a little under 16000 psi, which may or may not break the concrete down outright. Regardless, the saltwater and pressure are going to ensure a finite lifetime. The best source I could find on concrete's lifetime in seawater suggested (for some concrete types) repairing bridges made with non-marine concrete in about 10 years. Let's put the upper limit at 100 years, which seems ridiculously high for these conditions.
A lot of this is going to depend on Logan's physical condition. Is he actively straining against his slowly-deteriorating bonds, speeding up the process? When he finally busts out, as a superhero he'll probably be negatively buoyant, which means he'll have to swim a couple of hundred miles to the Mariana Islands, or much longer if he doesn't head in exactly the right direction.
Eventually, he'll reach land of some kind - whether it's ~150 miles to the Mariana Islands, ~1000 to Japan, the Philippines or China, or several thousand if he heads east and manages to miss the few islands between him and the United States.
If Psy-clops didn't convince the Super Squad not to search for Logan, they could conceivably find him once he's surfaced via search teams, satellite imagery, or Professor Chi's super power. If not, it's just a matter of discerning where he is and finding a cell phone.