After a week of Constantine in the game, I have finally found and captured him twice. Finding him has been easier than I expected (unless he's hidden so well more times than I'm aware of). I expected him to slightly creep parts of his body from behind objects, but every time I found him, his head was clearly visible (and once I got to each stage he's at, the game just happened to be at the spots Constantine was hiding at).
First time I saw him, I kept tapping him. It took a few seconds before a notification of capturing him appeared. I had wondered if I had done something wrong or if I just didn't press my finger hard enough.