In two dimensions, each update can be done in $O(\lg n)$ time, by using a balanced binary tree data structure.

Let $F$ denote the set of points in the Pareto frontier.  Store $F$ in a balanced binary tree, using the $x$-coordinate of each point as its key.

Now, given a new point $(x_q,y_q)$, you can check whether it is Pareto-dominated by any element of $F$ by finding the first element of $F$ to the right of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \ge x_q$ and $x$ is minimal); then checking whether it dominates $(x_q,y_q)$.   If not, you can check whether $(x_q,y_q)$ dominates any element of $F$ by finding the first element of $F$ to the left of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \le x_q$ and $x$ is as large as possible), and checking whether $(x_q,y_q)$ dominates it.  Then, you can use that information to decide whether you need to add $(x_q,y_q)$ to $F$ and whether there is any existing element of $F$ that needs to be deleted.

All of this can be done in $O(\lg n)$ time, using a balanced binary tree data structure.

This works in 2 dimensions (i.e., 2-tuples).  In higher dimensions, the problem gets much harder.  You can find references to the literature, with techniques for higher dimensions, at http://cs.stackexchange.com/q/40142/755; but I'm afraid that in high dimensions, all the known algorithms are likely to be fairly slow (they have a factor that is something like $O((\lg n)^{d-1})$ where $d$ is the number of dimensions).