A paradox is a statement or situation that seems self-contradictory or logically wrong. The most obvious paradox in Beloved is the seminal moment upon which the story hinges: Sethe's murder of her unnamed infant in order to save her (and indeed, her attempt to murder all of her children for the same reason).
It was not uncommon for slave women to drop their infants over the side of ships to cheat the slavers, so the murder of an infant by a slave woman was nothing unusual. What shocked everyone was how Sethe did it. In Beloved's case, she cut her throat with a handsaw, an act that requires a far greater force of will.
This paradox causes a rift between Sethe and Paul D, who, when he learns of what she has done, cannot understand--and she cannot explain it. She only knew that in her mind, slavery was far worse than death itself, so there was "logic" to her act: she took her child's life to save her from the worse threats of slavery (of rape, of being beaten, of losing herself and her individuality). Hers was an act of compassion, but is it compassionate to deny a child the chance at a life--any life? Thus, paradox.