I wonder how necessary the "directly adjacent" criteria is. Couldn't he sail from Russia to Iceland, for example? Perhaps if he was wanted by Interpol he would find it hard to travel through the territorial waters of European nations (assuming their coast guards would intercept a vessel carrying him).
In practice, though, I assume that Putin's government has made it very clear to him that his safety relies on him remaining a useful propaganda piece for the regime, so he wouldn't even get as far as Russian waters.